Unique BST's
Given an integer. Find how many structurally unique binary search trees are there that stores the values from 1 to that integer (inclusive).
Example 1:
Input: N = 2 Output: 2 Explanation:for N = 2, there are 2 unique BSTs 1 2 \ / 2 1
Example 2:
Input: N = 3 Output: 5 Explanation: for N = 3, there are 5 possible BSTs 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function numTrees() which takes the integer N as input and returns the total number of Binary Search Trees possible with keys [1.....N] inclusive. Since the answer can be very large, return the answer modulo 1e9 + 7.
Expected Time Complexity: O(N2).
Expected Auxiliary Space: O(N).
Constraints:
1<=N<=1000
Let's start by trying to solve the problem in Brute-Force manner. To form structurally unique BST consisting of n
nodes, we can start by taking any of the node 1...n
as the root node. Let the chosen root node be i
. Then, we have a BST where the root node is i
, the left child consist of all nodes from 1...i-1
(since left sub-tree must have only less than root's value) and right child consist of all nodes from i+1...n
.
1 1 2 3 3
\ \ / \ / /
3 2 1 3 2 1
/ \ / \
2 3 1 2
i = 1 i = 2 i = 3
(i = root node)
Now, we need to realize that the number of structurally unique BST formable with nodes having value i+1...n
is equal to the number of structurally unique BST formable with nodes having value i+1-i...n-i = 1...n-i
. Why? Because we only need to find BST which are structurally unique irrespective of their values and we can form an equal number of them with nodes from 1...n
or 2...n+1
or n...2n-1
and so on. So, the number only depends on number of nodes using which BST is to be formed.
Now, when we choose i
as root node, we will have nodes from 1...i-1
(i-1
nodes in total) in left sub-tree and nodes from i+1...n
(n-i
nodes in total) in the right side. We can then form numTrees(i-1)
BSTs for left sub-tree and numTrees(n-i)
BSTs for the right sub-tree. The total number of structurally unique BSTs formed having root i
will be equal to product of these two, i.e, numTrees(i-1) * numTrees(n-i)
. The same can be followed recursively till we reach base case - numTrees(0) = numTrees(1) = 1
because we can form only a single empty BST and single node BST in these cases respectively.
The final answer will be summation of answers considering all 1...n
as root nodes.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.