Total Number of BSTs using array elements as root node

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
11 upvotes
Asked in company
Microsoft

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
3
1 2 3
3
20 30 10
Sample Output 1:
2 1 2
1 2 2

Explanation for sample output 1:

Test case 1:

We will have the following trees :

With 1 as root node:

TC-1

The above 2 BST are possible.

With 2 as the  root node :

TC-2

Only this one BST is possible.

With 3 as the root node:

TC-3

The above 2 BSTs are possible.

Hence we return the sequence '2 1 2'.
Sample Input 2:
2
5
1 2 3 4 5
6
2 6 7 3 8 5
Sample Output 2:
14 5 4 5 14
42 10 14 14 42 10
Explanation for Sample Input 2:
Test Case 1: For the first test case, with 1 as the root node we will have 14 unique BSTs. Similarly for 2,3,4,5 as root nodes, we will have 5,4,5,14 unique BSTs respectively.

Test Case 2: For the second test case, with 2 as the root node we will have 42 unique BSTs. Similarly for 6,7,3,8,5 as root nodes, we will have 10,14,14,42,10 unique BSTs respectively.
Hint

Find all possible Binary Search trees for each element using Catalan Number.

Approaches (2)
Brute Force 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.
Time Complexity

O(N ^ 2), where ‘N’ denotes the number of elements present in the sequence.

 

Each iteration will take order of ‘N’ time as we need to iterate through total n elements and find the Catalan number which takes an order of ‘N’ time. Hence the overall time complexity is the order of  N ^ 2.

Space Complexity

O(N), where ‘N’ denotes the number of elements present in the sequence.

 

Output takes a space of order of ‘N’ as we need an array of 'N' elements to store the output sequence.

Code Solution
(100% EXP penalty)
Total Number of BSTs using array elements as root node
Full screen
Console