Removing an element from a Binary Search Tree in Python
Posted on Mon 24 October 2022 in Computing
💡 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:
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:
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).
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.
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.
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
Because the tree isn’t necessarily balanced, the worst case runtime would be O(N) or linear.