Leetcode–Unique Binary Search Trees

The Problem:

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

Notes:

  1. Writing down a few examples, we can observe a fact: for each i being the root, it has left subtrees of the number as i-1 nodes unique BST , its has unique right subtree of the number as n-i nodes unique BST. So we can use DP to solve the problem iteratively.

Java Solution

public class Solution {
    public int numTrees(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        int[] count = new int[n+1];
        count[0] = 1;
        count[1] = 1;
        count[2] = 2;
        int k = 0;
        for(int j = 3; j <= n; j++){
            for(int i = 1; i <=j; i++){
                //take i as the root
                count[j] += count[i-1] * count[j-i];
            }
        }
        return count[n];
    }
}
Advertisements

One thought on “Leetcode–Unique Binary Search Trees

  1. Pingback: Leetcode–Unique Binary Search Trees II | Linchi is coding

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