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

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
0 votes
0 votes

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  2n−1

answer is 64.

edited by
0 votes
0 votes

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  2n−1

Answer:

Related questions

73 votes
73 votes
5 answers
1