retagged by
49,477 views
168 votes
168 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$.
retagged by

17 Answers

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


 

edited by
5 votes
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 !!!!

4 votes
4 votes

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

3 votes
3 votes
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
Answer:

Related questions

73 votes
73 votes
5 answers
1