# Total Number of BSTs using array elements as root node

Posted: 22 Nov, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### For Example:

``````Let the sequence be 1, 4, 5, 6, 7 then return 14 5 4 5 14 i.e when 1 is the root node the number of BSTs possible is 14. Similarly, when 4 is the root node the number of BST’s possible is 5. In a similar way, we calculate the number of BST’s possible for the remaining elements of the sequence.
``````
##### Note:
``````1. Consider 0 based Indexing.

2. A Binary Search Tree is a special kind of tree in which each node of the tree has at most 2 children and for every node, the value of nodes of the left subtree of any node is less than the current node and value of nodes of the right subtree are greater than the current node.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the given sequence.

The next line contains ‘N’ space-separated integers denoting the sequence ‘ARR’.
``````
##### Output Format:
``````For each test case, print a single line containing 'N' space-separated which represents the number of BST’s that can be formed using each element of the given sequence as the root node.

The output of each test case will be printed in a separate line.
``````

#### Note:

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
1 <= N <= 10 ^ 3
- 10 ^ 9 <= ARR[i] <= 10 ^ 9

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of elements in the sequence.

Time limit: 1 sec.
`````` Approach 1
• The number of binary search Trees with ‘N’ nodes is given by the Catalan number.