In the BST built by inserting 50, 30, 70, 20, 40, 60, 80, the root 50 is deleted using its inorder successor. Which key becomes the new root?
Correct answer C. 60
Explanation
A node with two children is replaced by its inorder successor, the smallest key in its right subtree, found by going right once and then left as far as possible: 70, then 60. The key 60 moves to the root and its old node, a leaf, is removed. Using the inorder predecessor, 40, is also valid in general, but the question specifies the successor.
Answer checked How we write and check questions
Discussion