Last Updated: 22 Nov, 2020

Total Number of BSTs using array elements as root node

Moderate

Asked in company

Solve now

Problem statement

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In the previous approach, we saw that for calculating the number of elements less than and greater than the current element took linear time.

Also, we calculated the Catalan number for each element in linear time for each element in the sequence,

Can we do the above operations faster?

Yes! If we precompute the factorials till ‘2 * N’ in an array called ‘factorials’ then we can find the Catalan numbers in O(1) time.
For finding the number of elements less than and greater than the current element efficiently, we can make a copy of the given sequence, sort it, and then find the number of elements less than the current element in O(log N) by binary searching the current element in the sorted sequence.
Let the current element be at position ‘POS’ in the sorted sequence, then the number of elements less than the current element will be POS - 1 and the number of elements greater than the current element will be 'N’ - ‘POS’ - 1.
Then we find the Catalan number of ‘POS’ and 'N’ - ‘POS’ - 1 using our precomputed factorial array in O(1) time.
Finally, we multiply Catalan(POS) and Catalan(N - POS - 1) and return the product.

Keeping all this in mind we can take the following approach:

First, we create an array ‘ factorials’ and compute factorials of numbers till ‘2 * N’
Then we make a copy of the given sequence and name it ‘SORTEDCOPY’ and sort it.
Then we iterate through the given sequence and for each element we find its Position in ‘SORTEDCOPY’ using binary Search.
Let ‘POS’ be the position of the current element in the sorted array.
Then we find the Catalan number of ‘POS’ and store it in ‘ANSLEFT’.
Then we find the Catalan number of 'N - POS - 1’ and store it in ‘ANSRIGHT’
Finally, we return the product of ‘ANSLEFT’ and ‘ANSRIGHT’.

Solve now