CODEWITHSUNDEEP
data-structuresbinary-search-tree
Sumeet
Sumeet

Reputation: 8292

Find the number of possible binary search tree

Suppose, we have the keys 1,2,3,4,5,6,7. I have to find the total number of possible binary search trees such that height of binary search tree is 6.

The answer is 64. But I am not able to find a pattern so as to deduce the answer mathematically. Just by brute force drawing all possible trees is not possible.

One simple example of possible trees are skew unbalanced trees where the keys are inserted in ascending order and descending order. Both trees will be of height 6. But how to reach the total sum 64?

Upvotes: 2

Views: 89

Answers (1)

Rishit Sanmukhani
Rishit Sanmukhani

Reputation: 2269

This can be proved by construction.

Lets say,
F(n) = number of binary search tree with height n for n+1 numbers
Claim: F(n) = 2^n

Proof: 

F(0) = 1 (by construction)  
F(1) = 2 (by construction)

Now, to calculate F(n), then either the smallest number or largest number can be the root of the tree. Remaining n numbers will have to be arranged in the subtree on left (if largest number is root), or right (if smallest number is root)

So, 

F(n) = 2*F(n-1)  
F(n) = 2^n

Upvotes: 2

Related Questions