Unique Binary Search Trees

Problem Statement

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.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 Solution

class Solution {
public:
    int numTrees(int n) {

        if( n < 3 )
            return n;
        int i,j;
        vector numBST(n+1,0); /* numBST[i] - Number of Bst's upto i */
        numBST[0] = 1; /* '1' is just for multiplication */
        numBST[1] = 1;
        numBST[2] = 2;
        for(i=3;i<=n;i++)
        {
            int cnt = 0;
            for(j=1;j<=i;j++)
            {
                int left = j-1; /* No. of Elements in left side */
                int right = i-j; /* No. of Elements in right side */

                cnt += numBST[left] * numBST[right];
            }
            numBST[i] = cnt;
        }

        return numBST[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