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.