New update is available. Click here to update.

Last Updated: 23 Mar, 2021

Moderate

```
Given βNβ = 2, The total number of BSTβs is 2.
```

```
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.
```

```
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β.
```

```
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.
```

```
You don't have to print anything. It's been already taken care of. Just implement the given function.
```

```
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.