The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+67 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$
asked in DS by Boss (19.1k points)
edited by | 7k views
@Vikrant sir... it says the answer is 30...  so which one is correct 35 or 30 ?
Is the answer 64 or 35??please help :(
how do you get 64 @gari?

@Ahwan:- the link says answer is 35
yes, sorry, Its 35.

@gari In this question they hav told its insertion ... bt here its searching ... so different ..


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

explain ur approach ...

@srestha will u please tell in simpler manner by taking exapmles .I am very confused between this and


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


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 

both different case. Here certain condition is given , which u need to check

5 Answers

+81 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!}$

answered by Veteran (358k points)
edited by
@Arjun Sir:plz explain the ratio part ,how do we arrive to this?
please explain it???
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?
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 :)
awesome [email protected] sir
+20 votes

Question is similar to this question :

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

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$

answer = option A

answered by Boss (30.8k points)
edited by
50 is not bigger than 60 and it is red so i think there must be some typing mistake
+9 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
answered by Boss (31.6k points)
couldn't get You , sorry , can you clarify it again .
+7 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

answered by Boss (15.9k points)
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
+4 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)

answered by Active (2.6k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,716 questions
46,751 answers
58,407 users