Count number of binary search tree of height h for all possible roots over n elements

help
, ,
1

count number of binary search tree of height h for all possible roots over n elements

1 Like
2

I think this is called catalan numbers search on net…

1 Like
3

The question asks for trees of specific height h.
No. of trees over all h is a Catalan number.
Is it also true for specific h as in the question??

4

No,Catalan numbers are not the answer.

5

Then question is wrongly asked…

6

The answer is Catalan number only when there is no specific height requirements. And this is because Catalan numbers follow the recurrence dp[n] = dp[1] * dp[n-1] + dp[2] * dp[n-2] + … + dp[n-1] * dp[1].

7

This problem can be solved using the concept of dynamic programming.

Here we will require two states for dp :

first state i : this will denote that there are i nodes availabe to form the BST.
second state j : this will denote the height of the BST.

Therefore, dp[i][j] denotes the number of BSTs with height j that could be formed using i nodes

I will be creating the dp using top-down approach so we will be starting from the root and then go to the leaves likewise.

Lets say we put the value ‘x’ at the root node which will be at height ‘h’.

Since its a BST so its left child can have values from 1 to (x-1) and its right child can have values from (x+1) to n.

Now since we also need to take care of the height so we can say that the maximum height of either of its child must be ( h-1) .
Possible cases for above condition is :
case 1. Only left child is of height h-1.
case 2. Only right child is of height h-1.
case 3. Both child are of height h-1.

So for root to have a value x and height h its number of ways are :

value 1= dp[x-1][h-1] * ( dp[n-x][0] + dp[n-x][1] + dp[n-x][2] + … + dp[n-x][h-2] ) // case 1
value 2= dp[n-x][h-1] * ( dp[x-1][0] + dp[x-1][1] + dp[x-1][2] + … + dp[x-1][h-2] ) // case 2
value 3= dp[x-1][h-1] * dp[n-x][h-1] // case 3

val[x]= value1 + value2 + value3
// if root has value exactly x

Since root can have all values from 1 to n so,
dp[n][h]= val[1] + val[2] + … + val[n].

Each dp state can be computed using above approach.

Answer will be : dp[n][h].

18 Likes
8

No,The question asked is as correct as it can be.

9

Really a great explanation.
Thanks a lot