Number of binary search trees with N nodes

Tags: , , , ,

Number of binary search trees with n nodes

Given a number N, calculate number of binary search trees with n nodes those can be formed using number 1 to N as nodes. For example, with N = 3, there are 5 different trees which can be created as shown below.

number of binary search trees with n nodes

To solve the problem, let’s reduce the problem. 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.

number of binary search trees with n nodes

How about if N = 2, that is we have two nodes (1 and 2).  There are two binary search trees possible

number of binary search trees with n nodes

Now let’s take N =3. Five BST are possible as shown above in figure in example.

One observation is that every node becomes root at least one time. And when a number becomes root, all elements greater than the node form right subtree and all numbers less than root, for left subtree.

For every node i as root, all nodes on its left side  (from 1 to i-1 ) can form left subtree. Root of left subtree will be all numbers from 1 to i-1.
For node i  as root, all nodes on right side from i+1 to N will form right subtree. Root of right subtree of node(i) will be all numbers between i+1 to N.

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

Consider each node as root node and calculate number of trees possible. Add them together and we come to our solution.

Number of binary search trees with n nodes : Implementation

package com.company.BST;

/**
 * Created by sangar on 11.5.18.
 */
public class NumberOfBST {

    public static int numberOfTrees(int n){
        if(n <= 1) return 1;

        int sum = 0;
        int left = 0, right = 0;

        for(int i=1; i<=n; i++){
            left = numberOfTrees(i-1);
            right = numberOfTrees(n-i);
            sum +=  (left * right);
        }
        return sum;
    }

    public static void main (String[] args){
        System.out.print("Number of tress possible :" + numberOfTrees(3));
    }
}

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

Look at the execution of above implementation, see that some of subproblems are solved again and again.

number of bst with n nodes

We know that optimal solution to subproblems gives optimal solution to the original problem. Also, there are overlapping subproblems which are solved multiple times. These two conditions are the perfect for thinking in dynamic programming.  To avoid solving same problem multiple times, we use technique called memoization, where we will store solutions to subproblems which are already solved.

Let’s say T[i] represents number of binary search trees with i as root node.
What will be T[0] ? As there is one tree possible, empty tree with zero nodes, T[0] = 1. Again what about T[1]? We already saw that only one BST is possible with one node. T[1] = T[0] = 1

T[i] = Sum ( T[j] * T[i-j-1]) for j = o to i

package com.company.BST;

/**
 * Created by sangar on 11.5.18.
 */
public class NumberOfBST {

    public static int numberOfTrees(int n){
        if(n <= 1) return 1;

        int sum = 0;
        int left = 0, right = 0;

        for(int i=1; i<=n; i++){
            left = numberOfTrees(i-1);
            right = numberOfTrees(n-i);
            sum +=  (left * right);
        }
        return sum;
    }

    public static int numberOfTreesDP(int n){
        if(n <= 1) return 1;

        int[] T = new int[n+1];
        T[1] = T[0] = 1;

        for(int i=2; i<=n; i++){
            int sum = 0;
            for(int j=0; j<i; j++){
                sum += T[j] * T[i-j-1];
            }
            T[i] = sum;
        }
        return T[n];
    }

    public static void main (String[] args){
        System.out.print("Number of tress possible :" + numberOfTreesDP(4));
    }
}

Complexity of dynamic programming approach is O(n2) along with addition space complexity of O(n)

For more dynamic programming problem please refer : What is DP?

Please share if there is something missing or wrong. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us on communications@algorithmsandme.com