Unique BSTs

Hard
0/120
Average time to solve is 50m
profile
Contributed by
3 upvotes
Asked in companies
UberAmazonMicrosoft

Problem statement

Ninja is learning DSA to perform well in his college exams. He is learning about binary search trees. After learning about the properties of BST, he is curious to know that how many BST can exist for a set of given numbers. He wants to know all the unique BST having exactly N values from 1 to N.Can you help Ninja to form all the unique BST?

You are given an integer ‘N’.Your task is to return the list of the root node of all the unique BST having values from 1 to N.

For Example
If N is 3,all unique BST will be:

Example

Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of each test case contains a single integer, ‘N’, denoting the number.
Output Format:
For each test case, print the level order traversal of all the unique BST formed.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= N <= 8.

Time limit: 1 sec
Sample Input 1:
3
Sample Output 1:
1 -1 3 2 -1 -1 -1
1 -1 2 -1 3 -1 -1
2 1 3 -1 -1 -1 -1
3 2  -1 1 -1 -1 -1
3 1 -1 -1 2 -1 -1
Explanation of sample input 1:
For the first test case,

There exist 5 unique BST for the values 1 to 3. So, the given arrays are the level order traversal for each unique BST. (Empty Node is denoted by -1).

Example

Sample Input 2:
2
Sample Output 2:
1 -1 2 -1 -1
2 1 -1 -1 -1
Hint

Break the problem into smaller subproblems.

Approaches (3)
Recursion

In this problem, we can recursively form all the unique BST for the range 1 to N.So if we make root as ‘K’ then the left subtree will be constructed by range 1 to K-1. and right subtree as K+1 to N.

So, we will define a recursive function REC(i,j) that will return the list of roots of unique BST formed by numbers in range i to j. So if we make the root node with the value ‘K’.Then the left child will be among the list corresponding to REC(i, K-1) and similarly right child among REC(K+1,j).

At last, we will return the list corresponding to REC(1,’N’).

  

Algorithm:

 

  • Defining REC(i,j) function:
    • If i > j :
      • No tree can be formed.
      • Return a list having an empty Node.
    • If i == j:
      • Only one value. Only one tree exists.
      • Return [new Node with value as i].
    • Set ‘ANS’ as an empty list.
    • For ‘K’ in range i to j:
      • Set LEFTNODES as REC(i, K-1).
      • Set RIGHTNODES as  REC(K+1,j).
      • For L in LEFTNODES:
        • For R in RIGHTNODES:
          • Set NODE as the new node with value as K.
          • Set NODE’s left child as L.
          • Set NODE’s right child as R.
          • Append NODE to ‘ANS’.
    • Return ‘ANS’
  • Return list corresponding to  REC(1, N).
  • Return REC(1,N).
Time Complexity

O(N^N), where ‘N’ is the given number.

 

In this approach, we use recursive functions and each recursive function whose recurrence relation can be represented as O(n) = O(i)*O(n-i) for all i in range 1 to n.On solving this equation, the asymptotic complexity comes out to be O(N^N). Hence, the overall time complexity is O(N^N).

Space Complexity

O(N^N), where ‘N’ is the given number.

 

In this approach, O(N^N) space will be used by the memory stack in recursion for each recursive state. Hence the overall space complexity is O(N^N).

Code Solution
(100% EXP penalty)
Unique BSTs
Full screen
Console