Last Updated: 23 Mar, 2021
Unique Binary Search Trees
Moderate
Asked in companies
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.
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.
Approaches
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.
The main idea is to use Catalan numbers. In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects.
- Instead of doing it, like in DP and recursion, there is a well-known formula to calculate Catalan Number, which is :
- C(n) = Ci(2n, n) / (n + 1)
- where Ci: Binomial Coefficient.
- The Catalan number can be calculated by looping from 0 to ‘k’ where ‘k’ is the subscript in C, and multiplying (n - i), where i ranges from [0, k].
- Then divide it by (i + 1).
- Return the final answer.