Icarus and BSTCOUNT

Hard
0/120
profile
Contributed by
1 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
Hint

Use Divide and Conqure technique.

Approaches (1)
DP on Trees
  1. As root node in each tree/subtree will be fixed. We can divide the tree into the left subtree and right subtree.
  2. After calculating the permutations modulo (10^9+7) for the smaller subtrees we just have to calculate the number of permutations modulo (10^9+7) in combining the two subtrees.
  3. We will use this strategy until we reach the root.
  4. This hints to a divide and conquer strategy or Dynamic Programming on tree.
  5. We can calculate the number of permutations of the tree after combining the subtrees can be calculated as :
    • Let the size of left subtree be x and right subtree be y.
    • Then the number of ways of combining = (x+y)!/(x!*y!).
    • The number of ways of permutation will be = The number of ways of combining * number of permutations for left subtree * number of permutations for right subtree.


 

The steps are as follows : 

  1. We will precompute :
    • Size of subtree rooted at node ‘i’ .
    • Factorials modulo (10^9+7) for all numbers from ‘1’ to ‘N’. As calculating the number of ways of combining the subtrees will be costly when we combine the two subtrees.
  2. We will store the answer for each subtree rooted at node ‘i’ in a DP array.
  3. Traverse the tree using inorder traversal. In each call, we will first calculate the answer for the subtrees.
  4. Using the answer of the subtree we will caluculate the answer for the node as :
    • Let, size_of_subtree[right_child_of_node] = x;
    • Size_of_subtree[left_child_of_node] = y;
    • DP[node] = ( (x+y)!/(x! * y!) ) * (Dp[right_child_of_node] * Dp[left_child_of_node]).
    • Note, we will use modulo multiplicative inverse to calculate the result of (x+y)! / (x! * y!).
  5. We output DP[root] - 1 as we have to subtract the given subtree from our total permutations.
Time Complexity

O( N + N * log(N) ), where ‘N’ is the number of vertices in the tree.

 

Calculating the factorial up to ‘N’ takes ~N time.

Iterating the tree takes ~N and for each subtree, calculating modulo inverse takes ~log( N ) time.

Hence the overall time complexity is O( N + N * log(N) ).

Space Complexity

O( N ), where ‘N’ is the number of vertices in the tree.

 

Storing the DP values, factorial takes ~N space. 

Hence, the overall Space Complexity is O( N ).

Code Solution
(100% EXP penalty)
Icarus and BSTCOUNT
Full screen
Console