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.

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

C++:
01 int uniqueBST(int n)
02 {
03     int* A=new int[n+1];
04     for(int i=0;i<=n;i++)
05         A[i]=0;
06     A[0]=A[1]=1;
07     for(int i=2;i<=n;i++){
08         for(int j=1;j<=i;j++){
09             A[i]+=A[j1]*A[ij];
10         }
11     }
12     return A[n];
13 }
Advertisements
This entry was posted in Binary search, Dynamic programming. Bookmark the permalink.

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