3 / 6 Binary Search Trees, Rotations & Balance

Remove Then Add Back

Start from this binary search tree:

         8
       /   \
      4     12
     / \   /  \
    2   6 10   14

Remove 8. Since it has two children, the implementation promotes its inorder successor into the vacated node and deletes that successor from the right subtree. Then add 8 back with the ordinary insert.

Where does 8 end up?

A

Left child of 12, at depth 2

B

Right child of 6, at depth 3

C

Back at the root, giving the original tree

D

Left child of 10, at depth 2