When searching for the key value 60 in a binary search tree, nodes containing…
2007
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
- A.
35
- B.
64
- C.
128
- D.
5040
Attempted by 163 students.
Show answer & explanation
Correct answer: A
Key idea: ancestors less than the target must appear in increasing order and ancestors greater than the target must appear in decreasing order, so only the interleaving of these two ordered groups can vary.
Identify the two groups: values less than 60 are 10, 20, 40, 50 (4 nodes); values greater than 60 are 70, 80, 90 (3 nodes).
Within each group the order is fixed by BST structure: the smaller group must appear in increasing order, the larger group in decreasing order. So we only choose how to interleave the two groups.
Count the interleavings: there are 7 positions on the path and we choose which 4 of those positions are occupied by the smaller values (the remaining 3 are for the larger values). The number of ways is 7 choose 4 = 7!/(4!·3!) = 35.
Answer: 35
A video solution is available for this question — log in and enroll to watch it.