# 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:

- 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

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