5k views
The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is _________.

Note: The height of a tree with a single node is $0$.
retagged | 5k views
What if height=5 were asked in the question?

Although @Arjun ji has given correct answer. But one more way to think about this problem is at each level selection of one choice will generate two more choices. So  total no of ways are  --> $2*2*2*2*2*2*1 = 2^{6}$

We need to fill 7 levels with 7 elements. So, at each level we have exactly 2 possible options like 1 and 7 for root- one corresponding to making it left skewed and other right skewed. And this is the same for all levels up to 6 giving $2^6 = 64$ possible ways.
selected

Hi ... @Arjun Sir ..

Please explain the difference between the above question and

question mentioned here

https://gateoverflow.in/3462/gate2007-it-29

@Arjun Sir, we have 2 choices for each level means repetation is allowed.

ryt?
@Shubhanshu No. 2 choices mean that the child can either be a left child or a right child.
Root is fixed....so there are 2 choices for next node either it will be left subtree or right subtree....and subsequently for every node except root node there are 2 choices

Hence 2*2*2*2*2*2*1=64

@nitish both the questions can be solved in same way.

In the above question,

we can fix positions for all the nodes(i.e., node 1 to node 7) one by one and compute for all the cases and at last we can add all the cases.

for example,

for node 4 :- possible permutations are 6!/(3!*3!) = 20        ( _ , _ , _ , 4 , _ , _ , _ )

for node 1 (same for node 7) :- possible permutations are 6!/(6!*0!) = 1     ( 1 , _ , _ , _ , _ , _ , _ )

for node 2 (same for node 6) :- possible permutations are 6!/(5!*1!) = 6     ( _ , 2 , _ , _ , _ , _ , _ )

for node 3 (same for node 5) :- possible permutations are 6!/(4!*2!) = 15    ( _ , _ , 3 , _ , _ , _ , _ )

Total = sum of cases for all nodes = node1 + node2 + node3 + node4 + node5 + node6 + node7

= 1 + 6 + 15 + 20 + 15 + 6 + 1

= 64

WELL its RECURRENCE QUESTION ,,,,but for that need to observe the pattern ..first and then THE
RECURRENCE RELATION WILL BE N(h)=2N(h-1)

Thanks Deepesh superb explanation.

$N(h)= 2N(h-1)$ is the recurrence

& if we not take extreme elements then it is BST less than height 6 or it is not at all a BST.

So every level 2 Possibilities.

@deepesh Kataria thanks ...your explanation is great ... I was confused a lot before ... but now after your explanation it's all clear!

can you also explain this questionhttps://gateoverflow.in/3462/gate2007-it-29
@rajesh Pradhan nd thanks to u alot too because of u only I was able to identify Deepesh I mean I thought saare explainations upper se Jaa rahe the then I read ur feedback about Deepesh then Dhyan se dekha n read and got it

please explain the recurrence form i.e N(h) = 2N(h-1)

all clear @ Deepesh Kataria

A simple way to solve this question:
See that we need height of 6 and we have 7 elements at hand. So obviously any node in BST can't have two children.Now think about if root node is 2 or 3 or 4 or 5 or 6,then that root must have 2 children.So root must be either 1 or 7.Let denote root as 1st level.
So at 1st level, we either can choose 1 or 7(2 choices)
At 2nd level,similarly we can choose 2 or 6(2 choices)
At 3rd level,similarly we can choose 3 or 5(2 choices)
At 4th level,similarly we can choose 4 or 4(2 choices)
At 5th level,similarly we can choose 5 or 3(2 choices)
At 6th level,similarly we can choose 6 or 2(2 choices)
At 7th level, we will have only 1 number remaining.
So total number of BSTs possible=2^6=64
after 4,4 how wel eft with 2 choices, i mean we can't repeat numbers. @aritra nayak
very well
there can be total 2^6 skew tree ,and being a BST there is only one permumation for a given BST .

ytotal 2^6 diffrnect skew trees are possible

But  , here your resulting tree height must be 6.......

so it is only possible when your tree is either left-skew or right-skew ....

and above tree is binary search tree..........

so either you can insert in increasing order (right-skew tree) or insert in decreasing order (left-skew tree).....

so only possible way is 2....................

Emphasized point=>  (1) height must be 6      (2)  Binary search tree

left-skew or right-skew. But his can be changed for any level- at each level we got 2 options. So, $2^6=64$ ways (we don't need the entire tree to be left or right skewed).
But , @arjun sir , still confused the below condition must satisfy for above question (1) height must be 6 ( root element height is 0)... (2) tree must be binary search tree... (3) element are 1,2,3,4,5,6,7..... so , either you can insert your element in (increasing order)[1,2,3,4,5,6,7](right-skew tree) or decreasing order [7,6,5,4,3,2,1] left skew tree........ no other option are available....... if you try something other option .... tree's height not be 6............
ohk......got it arjun sir....clear the confusion.......
4

7

6

5

3

2

1

this is one kind of tree possible so ur answer is wrong
you can also from  start from 1 and make the same tree bending towards right and more like taking 1 as root after that seven as right child then 5 as left child and so on ..... and many more keep in mind that at each level you have to insert only single node and for each location you have two choice either choose smaller one or bigger one and their are 6 level so 2^6 = 64 possible trees
what do you mean by"we don't need the entire tree to be left or right skewed" ,then how will it fulfill the criteria of bst?
Arrange first all the nodes in asc or dsc order
Now observe 2 bottom nodes
U can come up with 2 bsts with that only 2 nodes
Now with three bottom nodes u get 4 bsts
Like wise
U get 2^6 at level 0
Since the height of the tree must be 6, it should have 6 edges intuitively the tree is skewed in this case.

Each edge has 2 choices i.e. it can a left branch or right branch. (/ or \)

So we can have 2^6 possible structures with height 6 and 7 nodes and for each structure there is only 1 way to fill up the values to form a binary search tree.

At root node 1 two choices left subtree or right subtree  = 21

At 2 there is also two choices = 22

------------------------------------------------

--------------------------------------------

at node 6 total choices either left or right subtree= 2

Hence total ways = 64

The Recurrence Relation for the no. of  binary search tree for 'n' nodes(distinct) with height 'n-1' will be

NBST(n-1)=NBST(n-2)+NBST(n-2) ;

Base condition:NBST(0)=1 and NBST(1)=2 ;

So NBST(6) =2*NBST(5)=2*2*NBST(4)=2*2*2*NBST(3)=2*2*2*2*NBST(2)=2*2*2*2*2*NBST(1)=26=64.

Eg:Take 3 nodes 1,2,3.No.of BST with height 2 is (i)With root as 1 ,the no. of possible BST will be 2(ie.NBST(1)) , (ii)With root as 3 ,the no. of possible BST will be 2(ie.NBST(1)) and (iii)With root as 2,there will not be any BST of height 2.

So 2+2 =4.

reshown by
at every level we should either select the minimum or the maximum as if we select any intermediate elements the hieght cant reach 6

so at level one 1 or 7  (7 elements left)

at level 2  either minimum or maximum of the remaining based on the selection at level 1 may be we select from 2,7 or 1,6 hence two choices this gives height 1  (6 elements left)

at level 3 either min or max this gives hieght 2 (5 left)

at level 4 min or max gives hieght 3 (4 left)

at level 5 min or max gives hieght 4  (3 elements left)

at level 6 min or max gives hieght 5  (2 elements left)

at level 7 we dont have choice 1 element left hence 2*2*2*2*2*2 gives 64