Number of binary search trees with n nodes

Number of binary search trees with n nodes

Given a number N, calculate number of binary search trees with n nodes, means BSTs that can be formed using number 1 to N as nodes.
Let’s take an example and work out the rule. What if there is only one node i.e N =1. There is only one tree possible with given node as root node and no children.

How about we have N=2, that is we have two nodes (1 and 2). Following are possible trees we can form using these two nodes.
Now let’s take N =3. Following trees can be formed using (1,2 and 3) as nodes.Find number of binary search trees with n nodes

Look closely, and see that every node becomes root at some point of time. And when a node becomes root, all elements which are greater than that node can form only right subtree and similarly, numbers less than root, they can form only left subtree.

So for each node i as root, consider that all nodes on its left side  ( from 1 to i-1 ) can form left subtree. Again root of that left sub tree can be any one of i-1 nodes. Getting some idea? Yes, it’s getting recursive. Same is true for right side for numbers i+1 to N.

Calculate number of left subtrees possible with given node i , call it l.
Then, calculate number of right subtrees possible with number i+1 to N and call it r. For each left subtree, there are r right subtrees with given root node.
So total number of trees which can be formed using i as root will be (l * r).

Consider each node as root node and calculate number of left and right subtrees possible. Add them together and we come to our solution 🙂

Simple way to check if answer for program is correct or not, calculate a number called as Catalan number. Calculate Nth Catalan number. Mathematically, Catalan number can be represented as

number of binary trees with n nodes

Code to find number of binary search tree with N nodes

#include<stdio.h>
 
int number_of_trees(int n){
	if(n <= 1) return 1;
 
	int i;
	int sum = 0;
	int left = 0;
	int right = 0;
 
	for(i=1; i<=n; i++){
		left = number_of_trees(i-1);
		right = number_of_trees(n-i);
		sum=  sum + (left * right);
	}
	return sum;
}
int main(){
        printf("\n%d", number_of_trees(3));
        return 0;
}

Notice that , some of the subproblems are being solved again and again during calculation. What is the method to use when we want to avoid solving subproblems again which are already solved? Yes, dynamic programming.
From formula to calculate catalan number, condition is quite evident

Trees[i] =  summation (j = 0 to i) of Tress[j] * Trees[i-j-1]
Tress[0] = Trees[1] =1

Number of binary search trees with N nodes: dynamic programming approach

#include <stdio.h>
int number_of_trees(int n)
{
	int i, j;
    // Table to store results of subproblems
    int Trees[n+1];
 
    // Initialize first two values in table
    Trees[0] = Trees[1] = 1;
 
    for (i=2; i<=n; i++)
    {
        Trees[i] = 0;
        for (j=0; j<i; j++)
            Trees[i] += Trees[j] * Trees[i-j-1];
    }
    return Trees[n];
}
 
int main(void) {
	printf("\n No. of trees: %d", number_of_trees(3));
	return 0;
}

Complexity of code to find number of trees which can be built using n nodes will be O(n!).

Please let us know if there is something wrong or missing. We would love to hear from you. Sharing is caring.

  • Hafeez

    ‘Print right view of binary search tree’ under problem list has wrong links.

    • http://algorithmsandme.com/ Jitendra Sangar

      Thanks for pointing out. Corrected it. Can you please let me know if you find any other broken or incorrect links. I have port blog from blogspot to WordPress, there may be places where things may not have gone correctly. Really appreciate it.

  • Hafeez

    ‘Print right view of binary search tree’ under problem list has wrong links.

  • Pingback: create binary search tree from inorder and preorder traversal – Algorithms and Me()

  • http://algorithmsandme.com/ Jitendra Sangar

    Fixed all,thanks for pointing out.