Icarus and BSTCOUNT

Hard

0/120

Contributed by

0 upvote

Problem statement

Icarus is given a binary search tree consisting of ‘N’ nodes. He have to find the different number of permutations of the tree nodes modulo 10^9+7. Where a permutation of a tree is an arrangement of nodes in the original tree such that the structure remains same but there exists at least one position in the permutation whose value is different from original tree.

Output the number of distinct permutations modulo 10^9+7.

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

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integers ‘N’, representing the number of nodes in the tree.

The second line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node) Refer to the example for further clarification.

Example :

Consider the binary search tree

The input of the tree depicted in the image above will be like : 
3
1 4
-1 2 -1 5
-1 -1 -1 -1 

Explanation :
Level 1 :
The root node of the tree is 3

Level 2 :
Left child of 3 = 1
Right child of 3 = 4

Level 3 :
Left child of 1 = null(-1)
Right child of 1 = 2
Left child of 4 = null(-1)
Right child of 4 = 5

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = null(-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

The different permutations of the tree are :
[3, 1, 2, -1, 4, -1, 5, -1, -1, -1, -1]
[3, 1, 4, -1, 2, -1, 5, -1, -1, -1, -1]
[3, 1, 4, -1, 5, -1, 2, -1, -1, -1, -1]
[3, 4, 1, -1, 2, -1, 5, -1, -1, -1, -1]
[3, 4, 1, -1, 5, -1, 2, -1, -1, -1, -1]

Output format :

For each test case, output an integer value denoting the number of distinct permutation of the tree modulo 10^9+7.

Print the output of each test case in a new line.

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^5
It is guaranteed that the given input is a binary search tree.

Time Limit: 1 sec

Sample Input 1 :

2
4
1 -1 2 3 4 -1 -1 -1 -1 
3
1 2 -1 -1 3 -1 -1

Sample Output 1 :

1
0

Explanation Of Sample Input 1 :

For test case 1 we have, 

The input tree:

The different permutations are :

[1, -1, 2, 4, 3, -1, -1, -1, -1]

Hence the answer is 1 % (10^9+7) = 1.

For test case 2 we have,

The input tree :

No other permutations exists for this tree.
Hence the answer is 0 % (10^9+7) = 0.

So, we output 1(true).

Sample Input 2 :

2
3
1 2 -1 3 -1 -1 -1 
3
1 2 -1 3 -1 -1 -1

Sample Output 2 :

0
0

Console