4.2k views

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 | 4.2k views
@Vikrant sir... it says the answer is 30...  so which one is correct 35 or 30 ?
how do you get 64 @gari?

yes, sorry, Its 35.

10, 20, 40, 50, 70 80, 90

In BST search we if we go from say 10 to 40 while searching for 60, we will never encounter 20. So, 10, 20, 40 and 50 visited, means they are visited in order. Similarly, 90, 80 and 70 are visited in order. So, our required answer will be

$\frac{\text{No. of possible permutations of 7 numbers}}{\text{No. of possible permutations of numbers smaller than 60 } \times \text{No. of possible permutations of numbers larger than 60} }$
(Since only one permutation is valid for both the smaller set of numbers as well as larger set of numbers)

$= \frac{7!}{4!3!}$

$=35$

selected
@Arjun Sir:plz explain the ratio part ,how do we arrive to this?
Need more explanation . Not able to follow
If the question ask Number of distinct BST instead of Number of orderings,then how answer will vary?

Question is similar to this question : https://gateoverflow.in/1275/gate2007_84-85

We will convert Moves to Text.
It is given that During Search we have Traversed these nodes

$\large \{{\color{Blue} 10, 20, 40}, {\color{Red} 50, 70, 80, 90}\}$

as it can be seen that Red ones are bigger than $60$ and blue ones are smaller than $60$.

Path to node $60$ has involved those nodes. So, one of the possible solution to the problem is $$\{L, L, L, S, S, S, S\}$$ any other solution will contains these moves only. coz at a time on a node we can get directions as S(meaning $60$ is smaller) or L(meaning $60$ is larger) on comparison and since its given that those nodes were encountered it means directions were picked from that set.

Hence, total number of possible solutions = all Permutations of that set, which is given by $\frac{7!}{4! \times 3!} = 35$

edited
50 is not bigger than 60 and it is red so i think there must be some typing mistake
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
couldn't get You , sorry , can you clarify it again .

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

Since all the keys are traversed while searching 60, we have to start with either 10 or 90 (2 possibilities for starting key).

Similarly., while traversing, 2 possibilities for every level  upto 6 levels and 1 possibility for 7th level (because there are 7 keys).

After doing this 60 can be found.

So 2^6=64 different orders possible.

Plz correct if Iam wrong @arjunsir
I also used this approach.