O(n) Solution Dynamic Programming


  • -1

    Base Case: a sequence of 1 element can generate just 1 Binary Search Tree

    Recursive Case: for a sequence of N elements we can take each of the elements i as root. The number of possibles BST taking the element i as root will be the number of combinations between all the possible BST generated from the elements on the left of the root, and all the possible BST generated from the elements on the right (the product).


    We cache the results for a sequence of length n to avoid computing multiple times the number of possible BST for the same length (Dynamic Programming).


    Here is the code implementing this solution:

       public static int numTrees(int n) {
    		int[] cache = new int[n+1];
    		cache[0]=cache[1]=1;
    		return nTrees(1,n,cache);
    	}
    	public static int nTrees(int left, int right,int[] cache) {
    		if(cache[right-left+1]>0) return cache[right-left+1];
    		for(int i=left;i<=right;i++) cache[right-left+1]+=nTrees(left,i-1,cache)*nTrees(i+1,right,cache);
    		return cache[right-left+1];
    	}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.