Unique Binary Search Trees

Unique Binary Search Trees

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

Example:

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

1

No Responses

Write a response