Consider the following binary search tree : If we remove the root node, which…
2016
Consider the following binary search tree :
If we remove the root node, which of the node from the left subtree will be the new root ?
- A.
11
- B.
12
- C.
13
- D.
16
Attempted by 602 students.
Show answer & explanation
Correct answer: D
Answer: 16
Explanation:
Key idea: When deleting a node with two subtrees, replace it with the inorder predecessor (the maximum node in the left subtree) or the inorder successor (the minimum node in the right subtree) to preserve BST ordering.
In the given tree, the left subtree of the root contains nodes 12, 11, 16, and 13. The rightmost (maximum) node in that left subtree is 16.
Replace the root value with 16, then remove the original 16 node from the left subtree. Because the original 16 has a left child 13 and no right child, attach 13 as the right child of 12.
Final structure after deletion: root = 16; left subtree root = 12 with children 11 (left) and 13 (right); right child of the root remains 26.