Total Number of BSTs using array elements as root node

Posted: 22 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a sequence array 'ARR' of ‘N’ integers. For each ARR[i] where 0 <= ‘i’ < 'N' , your task is to find the number of Binary search trees(BST) possible with elements of sequence ARR as nodes and ARR[i] as the root node.

The answer could be very large,so output your answer modulo (10 ^ 9 + 7). Also, use modular division when required.

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.
  • Read more about it here: https://en.wikipedia.org/wiki/Catalan_number
  • Now, for any element ARR[i] where ‘ARR[i] is the ‘i th’ element of the given sequence, to be the root of a Binary Search Tree, it is necessary that the elements in its left subtree are less than ARR[i] and elements in its right Subtree is greater than ARR[i].
  • Let the number of elements less than ARR[i] in the given sequence is ‘KL’ and the number of elements greater than ARR[i] in the given sequence is ‘KR’.
  • Then the number of unique BSTs with ARR[i] as the root node will be: Catalan(KL) * Catalan(KR) where Catalan(i) denotes the Catalan number for the integer ‘i’.

 

Keeping this in mind we can write the following solution:

  • Take a variable ‘K’ and for each ‘K’ in 0 <= ’K’ < N find the number of elements less than ‘ARR[K]’ where ‘ARR’ is the given sequence.
  • Let the number of elements less than ‘ARR[i]’ be ‘S’. So the number of elements greater than ‘ARR[i]’ will be a Total number of elements - S -1 i.e (N - S - 1).
  • Find the Catalan number of ‘S' and ‘N - S - 1’. Return the product of them.
Try Problem