Binary Search Tree Erase Idea

Binary Search Tree Erase Idea video (14 minutes) (Spring 2021)

Different cases

In a BST, a node can have either 0, 1, or 2 child nodes. If the parent node were to be deleted, in each of these cases:

0 children: This is easy, nothing happens. The deleted node is a leaf, and can simply be removed from the tree.

1 child: This is also easy. The deleted node would be replaced with the child node, similarly to deleting a node from a singly linked list. One pointer update happens. (And dynamically allocated memory is handled with a delete!)

2 children: This is trickier. We have two options to replace the deleted node.

Option A: replace the deleted node with the biggest element from the left subtree

Option B: replace the deleted node with the smallest element from the right subtree

For example, in this tree, if the root node 5 were deleted, it could either be replaced with 4 (option A), or 7 (option B) If 2 were deleted, it could be replaced with either 1 (option A) or 3 (option B)

            5
          /   \
         2      8
        / \    /
       1   4  7
          /
         3

We will use Option A for now. We will replace a deleted node with the biggest element from the node's left subtree.

The general Algorithm for Option A

1. Go as far right as possible in the left subtree (aka, find the biggest node in the left subtree)
2. This will be the largest node in the left subtree. It won't have any right subtree.
3. But, it may have a left subtree. Replace it with the biggest element in the left subtree.
4. This may result in recursive replacements.
5. Replace the originally deleted node with the node "fetched" in steps 1-3.

Thanks

Thanks for Brian Foster for writing up these notes based on the video lectures.