Suppose that we have numbers between 1 and 100 in a binary search tree and…
2006
Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?
- A.
{10, 75, 64, 43, 60, 57, 55}
- B.
{90, 12, 68, 34, 62, 45, 55}
- C.
{9, 85, 47, 68, 43, 57, 55}
- D.
{79, 14, 72, 56, 16, 53, 55}
Attempted by 176 students.
Show answer & explanation
Correct answer: C
Key idea: When searching for 55 in a binary search tree, each step imposes range constraints on subsequent nodes. Going right means subsequent nodes must be greater than the current node; going left means they must be smaller. These constraints accumulate from ancestors.
Start at 9: 9 < 55, so search goes right. Allowed range for later nodes: (9, +∞).
Next 85: 85 > 55, so go left. Range becomes (9, 85).
Next 47: 47 < 55, so go right. Range becomes (47, 85).
Next 68: 68 > 55, so go left. Range becomes (47, 68).
Next node is 43. But 43 is not in the required range (47, 68) because 43 ≤ 47. This violates the constraint imposed earlier by visiting 47 (which forced all later nodes on that branch to be greater than 47).
Conclusion: The sequence {9, 85, 47, 68, 43, 57, 55} is impossible because 43 violates the ancestor-imposed range (it cannot appear after moving right from 47). Therefore this sequence cannot be the sequence of nodes examined when searching for 55.