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

</aside>

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.

Given a Binary Search Tree:

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

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.