Testbook.com Test Series

Question

When searching for the key value 50 in a binary search tree, nodes containing the key values 10,15,20,30,60,80,89,90 are traversed, not necessarily in the given order. 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 50?

Comments

is the answer 70?

---

Yes. Could you please explain the solution. Thanks!

---

It is somewhat similar to gate Q-

https://gateoverflow.in/3462/gate2007-it-29

---

it is easy to see that at each point when we insert a new node in the bst it should be the extreme of the remaining values (either minimum or maximum) . so going this way  well get  2^7=128 total trees.But the thing to note here is that there are still some trees in which would not allow us to traverse  all the numbers when searching for 50.

for example consider the tree having 30 as the predecessor of 10,15 or 20.so when we encounter 30 while searching for our no 50 we would move to the right subtree thus will never encounter  10,15,or 20 .So lets count how many such trees  are there .Using some combinatorics u can find out that there are 29 such trees having 30 as the predecessor of 10,15 or 20.    Similarly 60 cannot be the predecessor of 80,89 or 90. here also we get 29 such trees.

so finally the answer is 128-2*29=70.

Hope this helps :)