retagged by
49,506 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

1 votes
1 votes

With n nodes, the maximum height that can be achieved is  n-1  when the tree is left or right skewed
here at each level, we have two choices except level 4 which has only one choice:-
two make tree skewed :
at level 1  (1,7)
at level 2  (2,6)
at level 3  (3,5)
at level 4  (4,4)
at level 5  (5,3)

and so on
so the number of ways is: 2*2*2*1*2*2*2 =64

1 votes
1 votes

We have been given 7 numbers and are asked to find the number of possible BSTs with height 6. This means that we have to find number of trees with maximum height.

How do we maximize height of a BST ? By skewing it ! How can we skew “effectively” ?

Maintain a list of available numbers and always pick the maximum or minimum from the list when choosing the next number in the ordering

Consider a small set of values : $\{1, 2, 3, 4\}$

  1. At the start all numbers are available.
  2. We can either choose $1$ or $4$. Let’s choose $4$, i.e. the maximum; the available set now becomes $\{1, 2, 3\}$
  3. We can either choose $1$ or $3$. Let’s choose $1$, i.e. the minimum; the available set now becomes $\{2, 3\}$
  4. We can either choose $2$ or $3$ and our tree has been formed.

In total, we made 3 independent binary decisions so the total possibilities are $2^3 = 8$. The 2 trees formed by taking $4$ first followed by $1$ are visualized below : (dot represents no children)

The same discussion can be extended for the given question as well to give the answer $2^6 = 64$

1 votes
1 votes

A Simple Alternative method:------

Assume a BST of Full binary Tree of height 6 (where root height is 0)

you can see from root to every  leaf node there is unique path ,

and total no. of this unique path is same as no. of possible ways in which elements {1,2,3, 4, 5, 6, 7 }  of height 6 BST can be created. (and in BST structure elements can be filled in unique way)

This unique path can is same as no. of leaves in full binary tree =$2^{height}$ (when height of root node is 0)

Hence answer is $2^{6}$ means 64

 

edited by
0 votes
0 votes

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

Related questions

73 votes
73 votes
5 answers
11