A binary search tree is used to locate the number 43. Which one of the…
2017
A binary search tree is used to locate the number 43. Which one of the following probe sequences is not possible during the search?
- A.
61, 52, 14, 17, 40, 43
- B.
10, 65, 31, 48, 37, 43
- C.
81, 61, 52, 14, 41, 43
- D.
17, 77, 27, 66, 18, 43
Attempted by 238 students.
Show answer & explanation
Correct answer: D
Correct answer: 17, 77, 27, 66, 18, 43 is not possible.
Use the valid range method while searching for 43 in a BST:
Start at 17. Since 43 > 17, move right. Now all later nodes must be greater than 17.
At 77. Since 43 < 77, move left. Now the valid range is 17 < value < 77.
At 27. Since 43 > 27, move right. Now the valid range becomes 27 < value < 77.
At 66. Since 43 < 66, move left. Now the valid range becomes 27 < value < 66.
The next value is 18, but 18 is not greater than 27. So this path cannot occur in a BST search for 43.
Why option A is possible: in 61, 52, 14, 17, 40, 43, every move keeps 43 within the narrowed range, so it does not violate the BST property.