Removing an element from a Binary Search Tree in Python

Posted on Mon 24 October 2022 in Python, Programming, Algorithms

💡 Note: Balancing the Binary Search Tree is out of scope for this blog post.

I’ve been taking Codecademy lessons recently and one of the bonus exercises was to figure out how to delete an element from a binary search tree. I figured I’d give it a shot.

class BinarySearchTree:
    def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None

Given a binary search tree, you can imagine our working tree to be this image below:

A binary search tree with 15 at its root, and the other numbers from 12 to 18 are perfectly placed within the binary search tree.

Example 1: Removing node 15, the parent node (Tree Rotation)

Removing 15 from the tree means that you’ll have two separate trees. To balance this all out, we can do a tree rotation.

First, we will get rid of 15 and make 16 the parent:

Two halves of the broken down binary search tree. Since 15 has been removed, its left and right children are orphaned. The right child, node 16, becomes the new parent and 14 is still orphaned.

Next, because the original left node (14) is orphaned, we would like to move 14 to be the leftmost node of the original tree (which would leave us with node 17).

The orphaned node 14 from the previous figure is appended to the leftmost node (17) of the new parent node (16).

We then add node 14 and its children to the previous leftmost node which is 17.

Example 2: Removing node 18, a node without children

The work for this is straightforward. We remove Node 18 and we will not have to do any other operations. As you will see in the code below, 16 basically just de-references 18 and we’re good as gold.

Our working Binary Search Tree without node 18.

Example 3, Removing node 17 (Shift Left)

Removing 17 is pretty simple still because node 17 only has a left child. This means that we move node 14 to node 17’s position and not have to worry about an orphaned right node.

The Binary Search Tree without node 17. Node 14 has shifted left and replaced node 17.

The Code

def remove_dft(self, value) -> bool:
    if self.value == value:
        if self.right:
                # Move right node up to be the parent, then do tree rotation
                self.right_rotation()
            elif self.left:
                # Move left node up to be the parent
                self.left_shift()
            else:
                # No children, this node needs to be de-referenced
                self.value = None
                return True

    if self.left:
        found = self.left.remove_dft(value)
        if found:
            # Dereference empty node
            if self.left.value == None:
            self.left = None
            return True

    if self.right:
        found = self.right.remove_dft(value)
        if found:
            # Dereference empty node
            if self.right.value == None:
                self.right = None
                return True

    return False

def left_shift(self):
    if self.left:
        # Shift left node to be the parent
        self.value = self.left.value
        self.right = self.left.right
        self.left = self.left.left
        return True

    return False

def right_rotation(self):
    if self.right:
        # Rotate right node up
        self.value = self.right.value
        self.right = self.right.right

        # Move orphaned left node into the leftmost node of the new parent
        orphaned_left_node = self.left
        if orphaned_left_node and self.right and self.right.left:
            leftmost_node = self.right.left
            while leftmost_node.left:
                leftmost_node = leftmost_node.left
            leftmost_node.left = orphaned_left_node
        else:
            self.left = orphaned_left_node

        return True

    return False

Runtime

Because the tree isn’t necessarily balanced, the worst case runtime would be O(N) or linear.

Previous Post Next Post