What will be the root after deleting it from a binary search tree?

Question

I am looking at this question:

Is the solution going to be node 23 because we would first apply a left-right rotation and then a deletion?

Answer 1

There are different algorithms for deleting a node from a binary search tree.

One is as follows:

• If the node is a leaf, then just remove it and stop
• If the node has one child, then replace the node by its child and stop
• If the node has has two children:
  • find the node's predecessor (its in its left subtree)
  • Copy that predecessor's value in the original node
  • Delete the predecessor node by applying one of the first two steps above.

The given tree has a root with two children, so we first find its predecessor, which is the node with value 23. Then that node (its value) is moved to the root node, and in its stead comes the node with value 19:

           50                    23
         /    \                /    \
       17      72      =>    17      72
     /   \    /  \          /  \    /  \
   12    23  54  76       12   19  54  76
  /  \   /               /  \
 9   14 19              9   14

The resulting tree is still balanced, so no rotations happen here. Moreover, the type of rotations to apply may depend on which type of self-balancing binary search tree is implemented: AVL, Splay tree, Red-black tree are examples of such trees which will rotate in different conditions and at different places in the tree.