BST Operations: Pseudocode (Part 4)

removeNode

Removing a node from a binary search tree is perhaps the most difficult operation on this data structure. There are three cases to consider when removing a node.

Case 1

The easiest case is when we remove a leaf node (a node with no children). We break the link between the node and its parent to remove the node from the tree.

See the example below, where we want to remove node 4. Node 4 is a leaf node so we can break the link between this node and its parent.

Case 2

The next case to consider is when we want to remove a node with only one child.

Assume we want to remove node 1. It is not a leaf node. It has a right child (node 2). If we break the link between 1 and its parent, we will also remove node 2, which is not what we want.

The solution is to replace the node to be removed by its only child. That is, the link from the parent of node 1 (which is node 3) will point to node 2, no longer to node 1. The effect is that this removes node 1 from the tree.

Case 3

Finally, the most difficult case is removing a node with two children (the children could have their children and so on).

Assume we want to remove node 6. 6 has two children, so the idea of taking its only child to replace node 6 does not work. However, we can do something similar. We need to find a node that can replace 6.

• Well, which node could satisfy the ordering property of the BST if placed at the position of node 6?
• Such a node needs to be bigger than all the nodes on the left side and smaller than all the nodes on the right side.
• A candidate node is the minimum value from the right subtree of 6. Think about it.
  • The minimum value from the right subtree of 6 is bigger than everything from the left subtree of 6 because it is bigger than 6 and 6 is bigger than everything on the left subtree.
  • The minimum value from the right subtree of 6 is smaller than all the other values from the right subtree of 6 since it is the minimum.

Concretely, in our example, we will replace 6 with the minimum value from its right subtree, which is 7 (the leftmost node in that subtree). The only problem is that now we will have two nodes with the value 7. But, the original node with value 7 has at most only one child (the right child) because the minimum is the leftmost node. If it also had a left child, it would not be the leftmost node, and therefore it would not be the minimum. We can call our remove function to remove this duplicate node and it will fall in either the first or second removal case.

See the following drawing for clarification:

Check that the resulting binary tree is still a binary search tree.

Note: It is possible to build multiple valid binary search trees from the same set of nodes. For example, during removal, we may choose the maximum value from the left subtree to replace the node instead of the minimum from the right subtree. The result will be a different binary ...