Unique Binary Search Trees

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

Example:

Input: 3
Output: 5
Explanation:
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

Before starting let us understand what Binary Search Trees are:

Trees which have left node smaller than the root and right node greater than the root are BST’s

Solution:

Let’s say for n = 0 and n = 1, Unique BST is 1

T[0] = 1;

T[1] = 1;

If n = 2, we can form 2 unique BST’s. First considering 2 as root node, 1 will be added to the left side as it is smaller than 2. Second, considering 1 as root and 2 will be added on the right side as 2 is greater than 1.

    2         1          
   / \    +  / \                
  {1} {0}   {0} {2}
T[1]*T[0]  T[0]*T[1]

T[2] = T[1] * T[0] + T[0] * T[1] = 1 + 1 = 2

If n = 3,

Lets first consider 1 as root, as 2 and 3 are greater than 1, it will be added to the right sub tree. The right subtree have 2 elements and we already know how many unique BST’s we can form if n = 2, we can use that value to compute for n=3. So basically we are going to solve the problem using dynamic programming

      1              
    /   \               
  {0} {2, 3}   
 T[0] * T[2] 

Now consider 2 as root, 1 will go to the left sub tree as it is smaller and 3 will go to the right sub tree

      2             
    /   \               
  {1}   {3}   
 T[1] * T[1]

Now consider 3 as root, 2, and 1 will be added to the left sub tree as it is smaller than 3.

     3            
   /   \               
{1, 2}  {0}   
 T[2] * T[0]

T[3] = T[0] * T[2] + T[1] * T[1] + T[2] * T[0]

T[3] = 2 + 1 + 2 = 5

Like wise we can solve the problem considering every element as root and using the previous results