GATE CSE 2016 | Set 2 | Question: 40

Question

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

Comments

Number of nodes in a perfect binary search tree of height 6 is, $2^{6+1}-1=127$

Each path from root to leaf will give 1 tree having height, 6

Total number of paths will be equal to number of binary search trees of height 6

(Verify using inorder traversal of any path)

Total paths = Total leaf nodes of perfect binary search tree 

Number of nodes = 127 = 64 + 63

Number of internal nodes = 63

Hence, number of leafs = number of bsts = 64

---

The rule for each step is:

At every step, the chosen element must be either the minimum or the maximum of the currently remaining uninserted elements.

---

Variation 1: what if they ask the resulting tree has height at most 6. ? ans is below.

ans = catalon no.

Variation 2: what if they ask the resulting tree has height at most 5. ? ans is below.

ans = catalon no. - 2^n.   (n = 6)
 

Answer 1

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$

Answer 2

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

Answer 3

Single node have height 0.So, for height 6 tree should have 7 level as we have 7 values i.e. every level have exaclty 1 value to get tree of height 6.

to get this kind of tree every node should have either minimum or maximum of remaining node otherwise more than 1 node will be there at some levels.

so from 1 to 6 level we have 2 choices that is maximum or minimum of remaining values in the sequence and at last level we will have no choice as only 1 value will be left so it will be filled as it is in tree

this is how we got 2^6.

• At 1st level: remaining are 1,2,3,4,5,6,7

             choice is 1 or 7 that is either max or min, suppose we took 1 as root.

• At 2nd level: remaining are 2,3,4,5,6,7

             choice is 2 or 7 that is either max or min, suppose we took 7.

• At 3rd level: remaining are 2,3,4,5,6

             choice is 2 or 6 that is either max or min, suppose we took 2.

• At 4rth level: remaining are 3,4,5,6

            choice is 3 or 6 that is either max or min, suppose we took 3.

• At 5th level: remaining are 4,5,6

            choice is 4 or 6 that is either max or min, suppose we took 6.

• At 6th level: remaining are 4,5

            choice is 4 or 5 that is either max or min, suppose we took 4.

• At 7th level: remaining are 5

            no choice i.e. single element remaining so take as it is.

 

Answer 4

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)=2⁶=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.

Answer 5

The number of ways in which n numbers x1<x2<⋯<xn can be inserted in an empty binary search tree, such that the resulting tree has height n−1 is  2ⁿ⁻¹

answer is 64.

Answer 6

The number of ways in which n  numbers  x1<x2<⋯<xn can be inserted in an empty binary search tree, such that the resulting tree has height n−1  is  2ⁿ⁻¹