Problem

Submissions

Hints & solutions

Discuss

Unique Binary Search Trees

Moderate

0/80

Average time to solve is 20m

Contributed by

11 upvotes

Asked in companies

Problem statement

You are given an integer ‘N’, your task is to return the number of structurally unique BST's (binary search trees) which have exactly 'N' nodes of unique values from 1 to 'N'.

For example:

Given  ‘N’ = 2, The total number of BST’s is 2.

Note:

1. A binary search tree is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

2. A structurally unique binary search tree is a tree that has at least 1 node at a different position or with a different value compared to another binary search tree.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains an integer 'N', the number of ‘nodes’.

Output format :

For each test case, print a single line containing a single integer denoting the total number of BST’s that can be formed. The output of each test case will be printed in a different line.

The output of each test case will be printed in a separate line.

Note :

You don't have to print anything. It's been already taken care of. Just implement the given function.

Constraints:

1 <= T <= 25
1 <= N <= 30

Where ‘T’ is the total number of test cases, and N is the number of nodes.

Time limit: 1 sec.

Sample Input 1 :

2
3
2

Sample Output 1 :

5
2

Explanation of the Sample Input 1:

For the first test case:
For N = 3, below are the possible BST’s that can be formed :

For the second test case: 
For N = 2, below are the possible BST’s that can be formed :

Sample Input 2 :

2
1
4

Sample Output 2 :

1
14

Hint 1

Hint 2

Can you do this by recursion?

Approaches (2)

Approach 1

Approach 2

Recursion

The main idea is to calculate all possible configurations using recursion.

Let numTrees( i ) denote the number of nodes on the left side of the root.
That implies numTrees(n - i - 1) denotes the number of nodes on the right side of the root.
Hence the total number of BSTs possible will be : numTrees(i) * numTrees(n - i - 1) for a given root.
Total number of BSTs possible will be : n * numTrees(i) * numTrees(n-i-1) , where n is number of different root configurations.
Therefore loop from 1 to n and for every ‘i’ add numTrees(i) * numTrees(n-i-1) to the answer.
Return the final answer.

Time Complexity

O(2 ^ N), where N is the number of nodes BST should have.

For every ‘i’th index, we have to choices to make hence the net, Time Complexity: O(2 ^ N).

Space Complexity

O(2 ^ N), where N is the number of nodes BST should have.

Space complexity will be the product of the height of the recursive call tree and the space used in one call. Thus, the final space complexity will be O( 2 ^ N).

(100% EXP penalty)

Unique Binary Search Trees

Console