Problem

Submissions

Hints & solutions

Discuss

Ninja and the BSTs

Moderate

0/80

Contributed by

0 upvote

Asked in companies

Problem statement

Ninja and Bob were playing the game. Ninja challenged Bob to solve the following problem.

Given an integer 'N' Bob has to find the total number of different binary search trees that can be formed with 'N' different nodes.

Your task is to help Bob to solve the task given by Ninja to him.

Print the answer modulo 1000000007.

Example:

Input: ‘N’ = 2
Output: 2
Explanation: We can form two different BSTs with two nodes only. 
One with node one as a root and the other with node two as a root.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer ‘T', denoting the number of test cases. 

Each test case contains a single integer 'N' denoting the number of nodes.

Output format :

For each test case, print the total number of different binary search trees that can be formed.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
1 <= 'N' <= 10^2
Timit Limit: 1 sec

Sample Input 1 :

2
1
2

Sample Output 1 :

1
2

Explanation Of Sample Input 1 :

With one node, only one possible BST can be formed.
With the two nodes, we can form two different BSTs. One with the first node as a root and the other with the second node as a root.

Sample Input 2 :

2
3
4

Sample Output 2 :

5
14

Hint 1

Hint 2

Hint 3

Try to think about in the recursive manner.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

Approach: We will start by taking any of the node 1...n as the root node. Let the chosen root node be i. Then, we have a BST where the root node is i; the left child consists of all nodes from 1...i-1 (since the left sub-tree must have only less than root value), and the right child consists of all nodes from i+1...n. We will recursively call it for all possible cases and count the number of BSTs.

Algorithm :

Check for base case if 'N' <= 1 return 1.
Initialize the variable 'ans' to store the answer.
Initialize variable ‘mod’ by ‘1000000007’
Run a for loop ‘i’ from 1 to 'N' and add the following multiplicand in the 'ans' numberOfBSTs(‘N’ - i) * numberOfBSTs(‘i’ - 1).
Update ‘ans’ with ‘ans % mod’
Return 'ans'.

Time Complexity

O(3^N), where 'N' is the number of nodes in the BST.

Asymptotically we will require to call the recursion 3^N times. Hence the time complexity will be O(3^N).

Space Complexity

O(N), where 'N' is the number of nodes in the BST.

Because of the space used by the function call stack during recursive function calls, the overall space complexity will be O(N).

(100% EXP penalty)

Ninja and the BSTs

Console