GATE IT 2007 | Question: 29

Question

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$

Comments

@Uma_Pravallika,

There are 13 answers on this question but still you're asking more explanation. Instead of that you can read all answers once and comment where you were feeling difficult to understand.  Then someone can help you.

---

Number of possible order $=$ Number of topological orderings of this graph $= \frac{7!}{3!4!}$

A must read blog: https://gateoverflow.in/blog/16797/permutations-and-combinations-specific-to-dag 

---

thank you!

Answer 1

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

Correct Answer: $A$

Comments

This is not possible since 80 is coming to the left of 70

---

it is not possible to follw that order beacuse you can place 70,50 in the correct way ,but you canonot place 80 in that order .So it is not possible to search the element .

---

@Akash Papnai

@Adrija

If the order was given as 10,20,50,60,70,80,90. And we have to search for value  60. Then the answer would be:?

(6!)/(3!*3!)

correct me if i'm wrong?

Answer 2

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,50},\color{red}{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, L, S, S, S\}.$$ Any other solution will contains these moves only because 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 it is 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$

answer = option A

Comments

https://stackoverflow.com/questions/32974943/how-many-different-orders-are-possible-in-which-the-key-values-can-occur-while-s

 

---

This is Combination with Repetation, IODB Template, right @Deepak Poonia sir?

Answer 3

In BST search we if we go from say 10 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.

It means that suppose we have 7 place now we have to select 4 places out of 7 for first 4 elements and we have to place them so , it can be done in $^7c_4$ =$\frac{7!}{3!4!}$ways

Possible arrangements can be

_10_ _ 20 40 50

Or 10_20_ 40_50

so we have to place in such a way that  they will follow the order 10,20,40,50 now for remaining elements 90 ,80,70 there is only one choice we can place them in one way  on 3 remaining places so,it will be $\frac{7!}{3!4!}$$^3c_3$ways but they should follow the order 90,80,70 

See--It can be placed on blank places as shown above 

90 10 80 70 20 40 50

Or 10 90 20 80 40 70 50

Answer -$\frac{7}{3!4!}$$^3c_3$=35

(For better understanding You can draw a tree in the order which I had follow)

Comments

Please can you elaborate why 9,8,7 should be in order?

---

@RohitParida, If they are not in order it will violate the BST property. Suppose if 80, 70, 90 is the order, the tree will have 70 and 90 as left and right child of 80 and we cannot have these when were are searching for an element. Check answer to this question, you'll understand https://gateoverflow.in/3385/gate-it-2008-question-71

---

Very logical explanation. Thanks!

Answer 4

Trying to explain it in the simplest way possible,

The thing we have to keep in mind here is that the elements before 60, i.e. {10,20,40,50} will always be in the same order and the elements after 60, ie {90,80,70} will always be in the same order, but the elements of the two sets can come between each other.

This means that the order  20, 40, 50, 90, 80, 70 is valid, but 10, 20, 90, 30, 40, 80, 70, 50 is also valid.

So imagine we have 7 places to be filled. _ _ _ _ _ _ _

We can chose the 4 elements to be filled in this 7 places in $_{4}^{7}\textrm{C}$ ways. (Not using permutation here as the order of the elements has to be maintained)

Now out of the remaining 3 places there is only choice for the elements of the second set because once the elements of the first set are in their respective places, the second set must appear in only one order: 70,80,90.

So total possible orders: $_{4}^{7}\textrm{C}$ *1 =35

Comments

nice approach

---

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

---

This means that the order 20, 40, 50, 90, 80, 70 is valid, but 10, 20, 90, 30, 40, 80, 70, 50 is also valid.

This means that the order 10, 20, 40, 50, 90, 80, 70 is valid, but 10, 20, 90, 40, 80, 70, 50 is also valid.

---

Finally found the most easy and best explanation!

 

---

Now, I get it.

Answer 5

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

Comments

@Kuljeet Shan 3 are the no of numbers in the order (90,80,70) we are selecting this 3 number sequence from the given 7 numbers as we want this order to remain intact. Alternatively, you can select the 4 numbers (10,20,30,40) i.e. 7c4 which will also have the same value.

---

Actually we can take any one of the sequence either smaller than 60 or grater than 60, both can give same answer.

If we take smaller values (i.e 7C4) there is only one choice for the larger numbers (i.e 90,80,70) to fill the empty places.

M i correct @Astha11 

---

Exactly! @Kuljeet Shan

Answer 6

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

Comments

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.

---

There is no 3 in the question,

Pls exaplain it