edited by
38,823 views
172 votes
172 votes

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$?

  1. $35$
  2. $64$
  3. $128$
  4. $5040$
edited by

13 Answers

16 votes
16 votes
10 20 40 50 shoyld appear in order similarly  90 80 70 shoyld appear in order

It is similar to grid problem of combinatorics

So 7c3=35 is ans
15 votes
15 votes

The sequences 10, 20,40, 50 and 90, 80, 70 can then be shuffled together, as long as their sub-sequences keep intact. Thus we can have 10, 20, 40, 50, 90, 80, 70, but also 10, 20, 90, 30, 40, 80, 70, 50.

but 10, 20 ,80,50,90,40,70 its not the possible sequencm when you make BST for it will be ambiguous coz of 90.

In the final 7 positions I have to choose 3 positions for the larger numbers (and the remaining 4 for the smaller numbers). I can choose these in 7C3=35.(73) ways

5 votes
5 votes

Path traversed during a binary search on a binary search tree is always a skewed tree.


The nodes {10,20,40,50,70,80,90} can be named as {b,b,b,b,a,a,a}.

(Here 'a' indicates after 60 and 'b' indicates before 60)
Now our work is just to find the number of permutations of the string {b,b,b,b,a,a,a}
= $\frac{7!}{4! \times 3!} = 35$

How does this work?
There is a fixed order among b's which is 10$\rightarrow$20$\rightarrow$40$\rightarrow$50
Similarly there is a fixed order among a's which is 90$\rightarrow$80$\rightarrow$70

Why this ordering is followed?

It is because we need to make our search progress towards our key=60, which is possible only by following the 2 orders: 10$\rightarrow$20$\rightarrow$40$\rightarrow$50 and 90$\rightarrow$80$\rightarrow$70.

Below I have tried some example strings.
(You can take another permutation and draw skewed tree for that permutation to have a better understanding)
Ex:
{b,b,b,b,a,a,a} => {10,20,40,50,90,80,70,(60)}
{a,a,a,b,b,b,b} => {90,80,70,10,20,40,50,(60)}
{a,b,a,b,b,b,a} => {90,10,80,20,40,50,70,(60)}


Hope this helps! :)
Let me know if there is any mistake here!

 

edited by
1 votes
1 votes

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 ?

 If we read the above underlined line of the question carefully, it is that how many key values can occur on the search path from root to the node containing value 60.

Nodes containing the key values are as 10,20,40,50,70,80,90. We have to reach upto the node containing value 60

So, take combination of first 4 keys which are lesser than 60 i.e 10,20,40,50 = 7C4

and for each combination of keys lesser than 60, there's a unique combination of keys greater than 60.

For eg: 10, 90, 20, 30, 80, 40, 70, 50

but the order of both groups of keys (lesser and greater) remains the same individually.

Therefore, 7C4 *1 = 35.

Source: https://stackoverflow.com/questions/32974943/how-many-different-orders-are-possible-in-which-the-key-values-can-occur-while-s#new-answer?newreg=dc372557efe3440da8bf0e91d44cb00b

Answer:

Related questions

62 votes
62 votes
11 answers
2
Ishrat Jahan asked Oct 29, 2014
28,939 views
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collide...