Unique BST Count
In this article, we will discuss the following problem:
Problem: Given a list of numbers from 1 to n, determine number of unique Binary Search Trees (BST) that can be generated from those numbers.
As established in the previous post, let’s understand the available information and what is required from the problem. In a real interview scenario, this step would correspond to clarifying and understanding the requirements thoroughly.
Analysis
Given :
List of numbers 1 to n
Is the list sorted ? To solve the problem, lets consider it is sorted. We will see later in the post that to solve the problem, it does not matter whether the list is sorted or not. But for time being, lets consider input list is sorted.
Required:
Distinct BST(s) that can be generated from the given list of numbers.
What is BST ? : Covered in the following section.
We need to determine the count of distinct BSTs.
Binary Search Tree
A binary search tree is a tree with the following property
All nodes to the left of the given node are lesser than the node.
All nodes to the right of the given node are greater than the node.
Example:
Consider the root node in the above tree which has a value of 21. All the nodes in the left subtree of 21 are < 21. All the nodes in the right subtree of 21 are > 21.
Likewise, considering any other node, say 30. All the nodes in the left subtree of 30 are < 30. All the nodes in the right subtree of 30 are > 30.
Approach
Let’s establish few fundamental concepts to solve the problem.
The placement of a new node in the tree depends on the value of the root node in the tree. If the new value is smaller than the root, the new value would go in the left subtree. If the new value is larger than the root, the new value would go in the right subtree.
For a given list of `n` numbers, there would be `n` different roots possible considering each value as the root node value once.
For each possible root value (say X), size of left subtree would be count of elements < X, size of right subtree would be count of elements > X.
Lets apply the above points to an example to eventually come with the approach.
Eg: Input: [1, 2, 3, 4, 5] , n = 5
Based on the point 2 above, each value in the input can be a root value once.
Considering 1 as the root node value
There will be no node in the left subtree as there is no element < 1.
There will be 4 elements (2, 3, 4, 5) in the right subtree.
Considering 2 as the root node value
There will be one element (1) in the left subtree.
There will be 3 elements (3, 4, 5) in the right subtree.
Considering 3 as the root node value
There will be 2 elements (1, 2) in the left subtree.
There will be 2 elements (4, 5) in the right subtree.
Considering 4 as the root node value
There will be 3 elements (1, 2, 3) in the left subtree.
There will be 1 element (5) in the right subtree.
Considering 5 as the root node value
There will be 4 elements (1, 2, 3, 4) in the left subtree.
There will be no node in the right subtree as there is no element > 5.
We can see a pattern here. The original problem was to determine distinct trees that could be generated from list of n values. Considering the case of 1 as the root value, it breaks down to determine distinct trees that could be generated from list with 4 values. Likewise, considering the case of 2 as the root value, original problem breaks down to 2 parts:
distinct trees that could be generated from list with 1 value (left subtree).
distinct trees that could be generated from list with 3 values (right subtree).
Base cases
n = 0
In this case, no tree can be generated so result will be 0.
n = 1
In this case, only one tree can be generated and that would be the root of the tree.
n = 2
In this case, 2 trees can be generated listed below. Irrespective of the values, there would be always 2 trees that can be generated from 2 values.
n > 2
Let the original problem be represented as countBST(n): count of distinct BST with n nodes. Based on the concepts established above and the example illustrated with list [1, 2, 3, 4, 5]
[I] Root as 1 : countBST(0) * countBST(4)
[II] Root as 2 : countBST(1) * countBST(3)
[III] Root as 3 : countBST(2) * countBST(2)
[IV] Root as 4 : countBST(3) * countBST(1)
[V] Root as 5 : countBST(4) * countBST(0)
we need to multiply as each distinct combination on left subtree can be applied with each distinct combination on right subtree.
countBST(5) = sum ([I], [II], [III], [IV], [V])
Implementation in Java
public int countBST(int n) {
// base conditions
if (n < 0) {
return 0;
}
if (n <= 2) {
return n;
}
int[] count = new int[n + 1];
count[0] = 1; //this should be 1 as we use it for multiplication
count[1] = 1;
count[2] = 2;
// solve for smaller indices, starting from 3 till n
for (int size = 3; size <= n; size++) {
int total = 0;
for (int index = 1; index <= size; index++) {
// count of nodes in left subtree * count of nodes in right subtree
total += count[index - 1] * count[size - index];
}
// set the value for sub-problem of size 'size'
count[size] = total;
}
return count[n];
}Variable `index` in the implementation represents ith element in list of size ‘size’.
Time Complexity : O(n2)
Nested for loops with upper bound of n to each loop.
Space Complexity: O(n), array with size n.
Extension:
Instead of numbers from 1 to n, what if the list contains any random integers. Suprisingly, the same solution applies in that case too. This is because any list of n numbers (not necessarily from 1 to n), will have n distinct roots (considering all elements are distinct). Each root value at i th position (in sorted list, we donot need to sort though) will have i - 1 values in left subtree and (n - i) values in right subtree.
Thanks for reading !, hope the solution was clear. Subscribe below to support my work.
If you are looking for solution to a specific problem, please drop the problem in comments and would work towards coming up with solution post for that.