# GATE2016-2-40

16.7k 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$.
in DS
retagged
2
What if height=5 were asked in the question?
7

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

0
BY MY OBSERVATION, I GOT THAT THERE ARE 2 WAYS TO SELECT FOR EACH EDGE,WHETHER IT SHOULD BE A RIGHT SKEWED EDGE OR LEFT SKEWED EDGE

EACH EDGE HAS 2 CHOICES 1 OR 7 ON IT'S END,2 OR 6 ON ITS END,3 OR 5 ON ITS END AND THE REST 4 IS THE ONLY CHOICE AT END,THERE ARE TOTALLY 2*2*2*2*2*2*1 CHOICES

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.

edited by
6

Hi ... @Arjun Sir ..

Please explain the difference between the above question and

question mentioned here

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

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

ryt?
13
@Shubhanshu No. 2 choices mean that the child can either be a left child or a right child.
16
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
28

@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

0

Is the answer same for tree of height 5? pls explain.

3

No, in tree with height 5..would be other case and i think you can solve it like this...just assume that there are only 5 node...then you will get 25 and now 7th node could be placed remaining side(left or right) at evry node...

total no. of binary tree would be ...25*5   ??

2

We have to assume there is 6 nodes(height= 5) and then we will get $2^{5}$...is that so?because we have no option for last node...pls clear this

Also the 7th node can be in the remaining side of the 5 nodes(including root excluding leaf node) as you said.

So 25*5  binary trees of height 5.

0
can u plz explain clearly ..why tree with height 5 is different case??
0

Can you tell where to place the 7th element. I have placed the 6 elements as right -skew tree.

1-2-3-4-5-6 in 2^5 ways.  Where I can place the element 7, it can not be placed to the left of the nodes .

0
@ arjun sir what about level 4 , their is only one choice 4,4 .
0
please anyone help me to understand the concept, I can't get this
0

@Ayush Upadhyaya need help regarding Kash comment.

Check the case for leaf =4 : suppose using 6C3 I select {1,3,7} { 2,5,6} and then leaf 4. how a tree with height h can be constructed using such partition?

1

@tusharp-I too didn't get that method.I solved this one taking into account that tree of height 6 will have 7 levels and at each level, I have to choose an element from {1....7} in such a way that each node at each level has exactly 1 child.

Like at Level 1 from 1,2,3,4,5,6,7 you can choose either 1 or 7 otherwise if you choose any other element, then tree of height 6 won't be possible.

Suppose at Level 1, 7 is chosen, now I have 1,2,3,4,5,6.Now I have to choose 6 or 1.Seems like you have to select an element in a way at each level like it should behave as worst case of quicksort, if it were selected as pivot.

5
To get the tree of height 6, every level should contain only 1 node.
So to get such tree at each level we should have either maximum or minimum element from remaining numbers till that level. So no. of binary search tree possible is,
1st level - 2 (maximum or minimum)

2nd level - 2

3rd level - 2

4th level - 2

5th level - 2

6th level - 2

7th level - 2
= 2 × 2 × 2 × 2 × 2 × 2 × 1
= 26
= 64
0

@tusharp If you're taking leaf=4 then in one set, lets say Small denoted by S={1,2,3} will be there and in other set large L ={5,6,7} Now the permutations can be SSSLLL or LLSSLS (here S,S,S wherever they're present should be in 1,2,3 order only same with L) ..so total permutation can be (6! / 3! 3!) = 20

0

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

I have a doubt here,how did you get the value 6!/(3!*3!) ?? are you choosing 3 elements of remaining 6 elements to fill the places in  ( _ , _ , _ , 4 , _ , _ , _ ) ?

0

In the question https://gateoverflow.in/3462/gate2007-it-29 particular height is not decided.

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)

4
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.
1

@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

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

all clear @ Deepesh Kataria

0
beautiful explanation. Thanks !
0
Why do we choose the extremes only in this case?
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
0
after 4,4 how wel eft with 2 choices, i mean we can't repeat numbers. @aritra nayak
0
very well
0
thanks for the explanation bro :-)
0
Hello aritra

I marked your answer wrong as i found it right answer with wrong solution, observe more carefully , you will know why.
0

@Rupendra Choudhary Sir it's a good answer. Just edit it and make it right.

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

Let $f(n)$ be the number of the binary search trees of $(n-1)$ height (i.e. maximum height) using numbers $(x+1,x+2,x+3,...,x+n)$ where $x \in \mathrm{R}$.

For $n=1$, the answer is $1$ since there is only one node of height $0$. $\therefore f(1)=1$

For $n=2$, the answer is $2$ since there are two cases of height $1$ starting $2$ as root and $1$ as root . $\therefore f(2)=2$

For $n=3$, the answer is $4$.

Let's observe how $f(n)$ is growing from $f(n-1)$. We can add the $n^{\mathrm{th}}$ node taking as the root to the trees of $(n-1)$ nodes $(1,2,3,...,n-1)$. For this case of $(n-1)$ nodes, there are $f(n-1)$ trees. Still there are more cases to be taken. Take $1$ as the root and the rest $(n-1)$ nodes are $(2,3,...,n)$ for which there are also $f(n-1)$ trees. [ For example, we can add $3$ as the root to trees of two nodes $(1,2)$. Besides taking $1$ as the root, there can be trees using $(2,3)$.  That's why $f(3)=f(2)+f(2)=2+2=4$ ]

So $f(n)=\{\text{trees using }(1,2,3,...,n-1)\text{ nodes having }n^{\mathrm{th}}\text{ node as the root}\}+\{\text{trees using }(2,3,4...,n)\text{ nodes having 1 as the root}\}$

\begin{align}\therefore f(n)&=f(n-1)+f(n-1)\\ &=2f(n-1)\\&=2^2f(n-2)\\&=2^3f(n-3)\\&=\cdots\\&=2^{n-1}f(1)\\&=2^{n-1}; ~[\because f(1)=1] \end{align}

$\therefore f(7)=2^{7-1}=2^6=64$.

So the correct answer is $64$.

edited
1
Good recursive approach.
1

Nice explanation @techbd123

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

5
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).
0
1
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............
0
ohk......got it arjun sir....clear the confusion.......
1
4

7

6

5

3

2

1

this is one kind of tree possible so ur answer is wrong
0
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
0
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?

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

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

## Related questions

1
9.1k views
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0$. The maximum depth at which integer $9$ can appear is _________.
Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right subtree using New-order; Visit the left subtree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by: ... $1 \ 7 \ 6 * + \ 2 \ 5 \ 4 \ 3 \ * \ - \wedge -$
$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this ... operations put together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$
Suppose the functions $F$ and $G$ can be computed in $5$ and $3$ nanoseconds by functional units $U_{F}$ and $U_{G}$, respectively. Given two instances of $U_{F}$ and two instances of $U_{G}$, it is required to implement the computation $F(G(X_{i}))$ for $1 \leq i \leq 10$. Ignoring all other delays, the minimum time required to complete this computation is ____________ nanoseconds.