Problem of the day
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 ExampleIf N is 3,all unique BST will be:
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.
1 <= N <= 8.
Time limit: 1 sec
3
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
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).
2
1 -1 2 -1 -1
2 1 -1 -1 -1
Break the problem into smaller subproblems.
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:
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).
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).