BST Operation: Remove (How it works)

The remove operation in a BST implementation of OrderedSet ADT is a somewhat involved process! We will break it down to three scenarios.

  • Node to be removed is leaf: Simply remove from the tree.

                  50                             50
            /     \         remove(20)      /   \
          30      70       --------->    30     70 
          /  \    /  \                     \    /  \ 
        20   40  60   80                   40  60   80

  • Node to be removed has only one child: Copy the child to the node and delete the child

                  50                             50
            /     \         remove(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80

  • Node to be removed has two children:

    1. Find smallest key in the right subtree (in-order successor) of the node.
    2. Copy key of the in-order successor to the node and delete the in-order successor. 
                  50                           60
            /    \         remove(50)     /   \
          40      70       --------->    40    70 
                  /  \                            \ 
                60   80                           80
    • Note that the largest key in the left subtree (in-order predecessor) can also be used.

Exercise Remove 1717 from the following BST.

Solution

Either replace 1717 with the smallest value in its right subtree:

Or replace 1717 with the largest value in its left subtree: