Number of binary search trees on $n$ nodes of height up to $h$

Question

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$?

For example, if the number of nodes is $4$, then the total number of BSTs is $14$. Out of these $14$ BSTs I have to find out the number with height not more than $3$.

Answer 1

We define the height of a tree to be the length of a longest path from the root to a leaf (i.e. the number of edges (not vertices) that such a path contains).

Let $b(h,n)$ be the number of binary search trees with height at most $h$ containing $n$ distinct positive integers as their keys. If the $i$-th largest number is the root, then the left sub-tree must contain $i-1$ keys (the ones smaller than the $i$-th largest) and the right sub-tree must contain $n-i$ keys and both must be of height at most $h-1$. Therefore: $$ b(h,n) = \sum_{i=1}^{n} b(h-1,i-1) \cdot b(h-1,n-i) $$ Note that we have $b(0,0) = 1,$ $b(0,1) = 1$ and $b(0,k) = 0,$ $b(k,0)=1$ for any integer $k > 1,$ which takes care of boundary conditions.

Your example asks for $b(3,4)$ which is still just $14$, since all BSTs on $4$ vertices have height at most $3$. However what you probably meant was $b(2,4)$ which is $4$.

EDIT: Actually $b(2,4)$ is 6 (as was correctly pointed out by @Aayush Aggarwal). The $b(2,4)$ was the result of a miscalculation on my part. The general forumla given above is still correct.

Answer 2

b(2,4): binary search trees with 4 distinct vertices and height 2(Edges) should be 6:- vertices: 1,2,3,4

 1              4         3         3         2       2  
  \            /         / \       / \       / \     / \
   3          2         1   4     2   4     1   4   1   3
  / \        / \         \       /             /         \
 2   4      1   3         2     1             3           4

Answer 3

Let us assume that the number of nodes are $n$. Also, consider that $a_{n,h}$ represents the number of different binary trees with $n$ nodes having height $h$. We construct the solution recursively.

Consider that $m$ is the current root, then for a binary tree of height $h$ we consider two cases:

1. The left subtree has the height of $h-1$. Also, we know that the left subtree contains $m-1$ nodes. So, the number of binary trees with $m-1$ nodes and height are given by $a_{m-1,h-1}$. Now, the right subtree can have any height in $[0, h-1]$, so the number of ways of forming right subtree is given by $\sum\limits_{i=1}^{h-1}a_{n-m,i} $. Therefore, total ways in this case are: $ a_{m-1,h-1}\sum\limits_{i=1}^{h-1}a_{n-m,i} $

2. Now, consider that left subtree has a height less than $h-1$. Then, the right subtree(consists of $n-m$ nodes) must have a height equal to $h-1$ which is given by $a_{n-m, h-1}$. Now, the left subtree can have any height in $[0, h-2]$, so the number of ways of forming left subtree is given by $\sum\limits_{i=1}^{h-2}a_{m-1,i} $. Therefore, total ways in this case are: $ a_{n-m,h-1}\sum\limits_{i=1}^{h-2}a_{m-1,i} $

As we have $n$ different ways to choose the node, we have the number of different binary trees of height $h$ and $n$ nodes given by the following formula:

$a_{n,h}$ = $\sum\limits_{m=1}^{n} (a_{m-1,h-1}\sum\limits_{i=1}^{h-1}a_{n-m,i}+a_{n-m,h-1}\sum\limits_{i=1}^{h-2}a_{m-1,i})$

This recurrence relation can be solved using the base case as:

1. $a_{0,0}=1$
2. $a_{i,0}=a_{0,i}=0$, for all $i>0$

Hence the final answer to the original question becomes:

$A_{n,h}=\sum\limits_{i=1}^{h} a_{n,i}$