# Unique Binary Search Trees

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

**Example:**

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