Register

GATE Overflow Test Series | Mock GATE | Test 6 | Question: 43

• edited by
145 views
2 votes
2 votes
In a binary search tree, the following key values (not necessarily in the order given) are encountered while searching for the key $24.$
$$1,5,9,13,17,21,25,29,33.$$ The total number of possible orders in which the given keys of the binary search tree could have been visited is _________
• edited by
User Avatar

1 Answer

1 votes
1 votes
We have $9$ elements in the search path. Out of these $6$ are lower than $24$ and $3$ are higher than $25$. All the lower elements to $24$ must occur in an order and similarly all the higher elements to $24$ must also occur in an order. So, total possibilities $ = \dfrac{9!}{6!3!} = 84.$
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Arjun asked Jan 30, 2022
163 views
GATE Overflow Test Series | Mock GATE | Test 6 | Question: 16
What is the best time complexity for finding the lowest common ancestor for two keys $a$ and $b$ $(a < b)$ in a height balanced binary search tree of $n$? You can assume that both $a$ and $b$ exist in the tree. $\Theta(n)$ $\Theta(n \log n)$ $O(\log n)$ $\Omega(n)$
What is the best time complexity for finding the lowest common ancestor for two keys $a$ and $b$ $(a < b)$ in a height balanced binary search tree of $n$? You can assume ...
User Avatar
Link Copied!