Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
 Given n = 3, there are a total of 5 unique BST's.
 Screen Shot 2016-04-09 at 11.15.22 PM

 

public class Solution {
    public int numTrees(int n) {
        int[] count = new int[n+1];
        count[0] = 1;
        count[1] = 1; 

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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s