How to find the number of Binary Search Trees with given number of nodes and leaves?

Question

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:

• Exactly $1$ leaf node(s) present?
• Exactly $2$ leaf nodes present?

I was able to solve the first one(and the actual problem was also that, but then I though what if the process can be extended)

Here's my take on the 1st one

Here the elements are  $1,2,3,4,5,6,7$ (let's assume that for simplicity) and we need only $1$ leaf 

• So let us fix a root node: To fix the root node we have $2$choice either $1$ or $7$ from  $1,2,3,4,5,6,7$

• (if we select any non-extreme elements then only $1$ leaf is not possible)

• Let us say we select $1$ as root node 

• In each and every level we have $2$ different option that is to select i,e; either of extreme elements

• So in 2nd level we can select $2,3,4,5,6,7$

• Let us say we select $7$ in 2nd level 

• We still have 2 option to select in $2,3,4,5,6$

• So this is true in all levels except last level since only $1$ element is left.

• Therefore, total possibilities are : $2 * 2 * 2 * 2 * 2$ = $2^5$

The same condition is true for $7$ as a root

Hence, $2^5* 2$ (1 as root or 7 as root)  =  $2^6$.

(Which comes out as $2^{number of nodes -1}$)

But how can we now approach the second subpart or it can be generalized for let's say (2,3,4) leaf nodes?

• Exactly 2 leaf nodes present?

Answer 1

You can compute the numbers with dynamic programming.

Let $c(n,l)$ be the number of BSTs with $n$ nodes and $l$ leaves, where the nodes are selected from a set of $n$ distinct nodes. Then we have the following recurrence relation in general cases,

$$c(n,l) = \sum_{i=0}^{n-1}\sum_{j=0}^l c(i,j)\cdot c(n-i-1, l-j)$$

• The outer summation is over $i$, the number of nodes in the left sub-BST of a BST with $n$ nodes and $l$ leaves.
• The inner summation is over $j$, the number of leaves in the the left sub-BST of $i$ nodes.
• The product $c(i,j)\cdot c(n-i-1, l-j)$ is the number of BSTs whose left sub-BST has $i$ nodes and $j$ leaves and whose right sub-BST has $n-i-1$ nodes and $l-j$ leaves. Please note that the root of such BST has only one choice, namely, the $(i+1)^{th}$ smallest node.

I will let you figure out the boundary values of $c(n,l)$ such as when $n=0$ or $n=1$ or $l=0$. There might be a few different cases. However, this should be enough to point you to the right direction.