102 votes

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

Note: The height of a tree with a single node is $0$.

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

132 votes

Best answer

6

Hi ... @Arjun Sir ..

Please explain the difference between the above question and

question mentioned here

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

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

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 2^{5 }and now 7th node could be placed remaining side(left or right) at evry node...

total no. of binary tree would be ...2^{5}*5 ??

2

thank you @ hs_yadav

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 2^{5}*5 binary trees of height 5.

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

@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

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

148 votes

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.

$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

28 votes

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

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

16 votes

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

ytotal 2^6 diffrnect skew trees are possible

7 votes

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

5 votes

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

think about it !!!!

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

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

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