The Gateway to Computer Science Excellence

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

- $35$
- $64$
- $128$
- $5040$

+64

this is an awesome question, and here is the double awesome solution http://cs.stackexchange.com/questions/11043/number-of-possible-search-paths-when-searching-in-bst/11048#11048

0

@gari In this question https://gateoverflow.in/39586/gate2016-2-40 they hav told its insertion ... bt here its searching ... so different ..

0

@ Puja Mishra they are also saying it's a binary search tree.. so shouldn't we follow the convention ..please help

0

@srestha will u please tell in simpler manner by taking exapmles .I am very confused between this and https://gateoverflow.in/39586/gate2016-2-40

0

thereis a small difference between these two

Take a small example

Say 10,20

One question is saying how many order possible taking 20 as root? answer will be 1

Another question how many ways we construct BST of height 1? answer will be 2

10 20

\ /

20. 10

got it?

Take a small example

Say 10,20

One question is saying how many order possible taking 20 as root? answer will be 1

Another question how many ways we construct BST of height 1? answer will be 2

10 20

\ /

20. 10

got it?

0

ohk the link which I have been posted ,same bottom up approach I used and got result 2 ^6 .But for this question it is not mention in question tht 60 can be consider as root .Then?

0

then it be catalan number for BST

https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

okk?

0

here in this question if I am applying catalan number for unique BST it will give more than 35 ,but question is different here .I AM NOT ABLE TO UNDERSTAND PLS CLEAR THIS

0

@HeadShot

There he considered 90,80,70 to always come together which is not true. As the immediate next comment mentions that 10, 20, 90, 30, 40, 80, 70, 50 is also possible (30 was not there in the original question).

There he considered 90,80,70 to always come together which is not true. As the immediate next comment mentions that 10, 20, 90, 30, 40, 80, 70, 50 is also possible (30 was not there in the original question).

0

@HeadShot

Please elaborate your approach..because in the link you gave there he took 90,80,70 together

Please elaborate your approach..because in the link you gave there he took 90,80,70 together

0

@MiNiPanda

See.., 90,80,70 need not to be contiguous but must be in that order so does 10,20,40,50.

I think its satisfied with my approach , at the same time i know 35 is correct answer but i am not getting where i am going wrong.

+1

Hi @HeadShot,

I think i know why 64 is incorrect for this question. Kindly check how i am trying to disprove 64. Hope i am able to convince. Thanks

+12

Given the fact that all those nodes are visited before reaching 60. {10->20->40->50} and {90->80->70} these are the dependencies that must be preserved till reaching 60.

Co relating the first set as transaction T1 and second set as T2, we have to find all possible schedules.

hence 7!/4! . 3!

Just an analogy. :)

Co relating the first set as transaction T1 and second set as T2, we have to find all possible schedules.

hence 7!/4! . 3!

Just an analogy. :)

0

@Chaitrasj, thanks for explanation. But can the argument be made like this for disapproving ( you are presenting the same fact, but I am using different words). If we select 10 -> 90 -> 40 (here we don't left with choice of 20, 30,) since we choosen 40, as 20, 30 are less than 40 and since our search is for 60, So, we can never really reach those 20, 30 in this way. So in one sense there is never 2^6 choices?

+5

People like me who don't understand why the answer is not $64$, here is a hint.

For the answer to be 64, we have to have 2 choices every time, isn't it? But in this case, it is not like that...

That's why it can't be $64$, so try some other method.

+141 votes

Best answer

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

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$

+1

If the question ask Number of distinct BST instead of Number of orderings,then how answer will vary?

+29

each of the above permutations leads to one bst which is distinct so 35 BST's and the above approach is similar to the number of schedules possible with n1 operations in one transaction and n2 in other (n1+n2)!/n1!*n2! as the ordering of the operations shouldn't change :)

+3

Can anyone please explain that why we will not encounter 20 on traversing from 10 to 40 while searching for 60?

+1

Given no's traversed are 10,20,40,50,70,80,90 if these are already traversed then how no 60 can occur in between them if it occur then we never traversed to geater than 60 coz it's already found n if they are traversed then they will be surely in same path ,n that path height will be 6 so total order should be 2^6

0

This is what given solution everywhere but question can be interpreted two type first what the solution everyone giving second when coz all node are traversed n this is not necessary these are the only nodes in BST then while searching for 60 these all will be traversed ,that thay all will be in same path so height will be 6 so total order possbile will be 2^6

+3

@Dhiraj Raj Because( we have to search for 60).When we are at 10(we need to search 60), we'll go to an element greater than 10,say 40. When you are 40, to search for 60 you will move to element greater than 40.Moving to 20 after 40 is not correct

+13

10, 20, 40,50 and 90,80,70 will always come in this order since we have a binary search tree.

Ex. 10 20 40 50 90 80 70{S,S,S,S,L,L,L} or 10 90 20 40 80 70 50 {S,L,S,S,L,L,S}.

(S- no. Smaller than 60, L-no. Larger than 60)

So we have got 2 groups of 3 and 4 numbers each. Say, group 1={L,L,L} containing nos. >60, group 2={S,S,S,S} containing nos.<60. But group order remains same (10,20,40,50) and (90,80,70) so no need to worry about their permutations individually. Now, wherever we place S and L in 7 positions, S will be replaced in 10,20,40,50 order and likewise for L.

So out of 7 positions, we can place 3 larger nos. {L,L,L} in 7C3 ways=7!/4!*3!

(Which automatically includes combinations for choosing smaller 4 nos.)

Ex. 10 20 40 50 90 80 70{S,S,S,S,L,L,L} or 10 90 20 40 80 70 50 {S,L,S,S,L,L,S}.

(S- no. Smaller than 60, L-no. Larger than 60)

So we have got 2 groups of 3 and 4 numbers each. Say, group 1={L,L,L} containing nos. >60, group 2={S,S,S,S} containing nos.<60. But group order remains same (10,20,40,50) and (90,80,70) so no need to worry about their permutations individually. Now, wherever we place S and L in 7 positions, S will be replaced in 10,20,40,50 order and likewise for L.

So out of 7 positions, we can place 3 larger nos. {L,L,L} in 7C3 ways=7!/4!*3!

(Which automatically includes combinations for choosing smaller 4 nos.)

+35 votes

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

+21 votes

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,30,40 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)

+13 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

+2

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

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

+12 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

It is similar to grid problem of combinatorics

So 7c3=35 is ans

0

@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.

0

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

+8 votes

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

+2 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!

+1 vote

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.

52,223 questions

59,811 answers

201,020 comments

118,087 users