A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the…
2008
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?
- A.
II and III only
- B.
I and III only
- C.
III and IV only
- D.
III only
Attempted by 116 students.
Show answer & explanation
Correct answer: D
Correct answer: Only sequence III is possible.
Sequence I (81, 537, 102, 439, 285, 376, 305): fails at 285 -> 376. At 285 we go left because 273 < 285, so any next node must be less than 285, but 376 > 285, a contradiction.
Sequence II (52, 97, 121, 195, 242, 381, 472): fails at 381 -> 472. After 242 we go right to 381 (273 > 242), then since 273 < 381 the next node must be in the left subtree of 381 (i.e., less than 381), but 472 > 381, so this order is impossible.
Sequence III (142, 248, 520, 386, 345, 270, 307): consistent. Comparisons: 273>142 -> right to 248; 273>248 -> right to 520; 273<520 -> left to 386; 273<386 -> left to 345; 273<345 -> left to 270; 273>270 -> right to 307. At 307 we would then go left (273<307) and encounter a null child, so the search is unsuccessful. All visited nodes obey BST ordering constraints.
Sequence IV (550, 149, 507, 395, 463, 402, 270): fails at 395 -> 463. After reaching 395 we must go left (since 273 < 395), so the next node must be less than 395, but 463 > 395, which is a contradiction.
Thus only sequence III lists nodes in a possible order encountered during an unsuccessful search for 273 in a BST whose keys lie between 37 and 573.
A video solution is available for this question — log in and enroll to watch it.