Problem Link:
Difficulty:
Medium
Pre-requisites:
Trees
Problem:
You are given the preorder and the postorder traversals of a rooted K-ary tree. Find how many such trees are there having the given preorder and postorder traversals. Two trees are different if the children[] array for some node is different (see original problem statement for examples and details).
Quick Explanation:
Reconstruct the tree (without children-array information) if it is possible. If it is impossible to reconstruct the tree, return 0. If some node of the reconstructed tree has > K children, return 0.
Now, if a node v has x children, there will be Comb(K, x) ways of arranging them in v’s children[] array. Further, two ways will correspond to different trees by definition. Note that we can’t change the relative order of the children within the positions of children[] where we choose to fill them, since that would have produced different preorder and postorder traversals.
Now, to reconstruct the tree, use the following method. Lets say P1[i1…j1] matched with P2[i2…j2]. Then, we know that the root of the currently considered subtree is P1[i1] == P2[j2]. If these two don’t match, then we return 0.
After we match these, we take the first child - this would be at P1[i1+1]. We find at which position “i0” it is present in P2, i.e. P1[i1+1] = P2[i0]. There would be i0 - i2 + 1 nodes, and thus we would try to recursively reconstruct the subtree using P1[i1+1…i1 + i0 - i2 + 1] and P2[i2…i0]. Note, if i0 is not in the range [i2…j2], then the answer is 0. Also note that if the given permutations do not correspond to a valid preorder and postorder traversal, then at some point of our recursive reconstruction, we would get that this i0 falls out of the i2…j2 range of P2.
Once we have reconstructed the entire tree, we just calculate prod(K choose x) over all nodes v, where x is the number of children of the node v.
Detailed Explanation:
Let us first assume that we are able to reconstruct the tree. That is, we are able to get the following information:
(a) What is the root of the tree
(b) For each node, what are the children of that node
© And also, in what order do the children appear in the children[] array.
We will later see that the preorder and postorder traversals, if valid, do give us all the above information.
Now, given the value of K, for a node n having x children, there will be Comb(K, K-x) ways of picking up positions in the children[] array such that we fill in null at those positions. Given that we have filled in null at those positions, and the fact that the order of the children in the children[] array is uniquely defined, we will fill in the remaining positions of the array uniquely. Thus, there are Comb(K, x) ways of filling in the array for a node n having x children.
Also, for two different nodes, the way we arrange the elements of the children[] array are completely independent. Thus, the entire original rooted K-ary tree can be got by fixing some particular way of filling in the children[] array for each of its nodes. This implies that the total number of such trees is merely prod(Comb(K, x)) over all nodes n, where x = number of children of n.
To reconstruct, let us go step by step, seeing what all information we have, and what all does that imply for us.
Root: P1[0] is the root of the tree. P2[N-1] is also the root - which means the two had better be the same.
First child: P1[1] is the first child of the root. Lets say P1[1] = n. Lets look at the position of n in P2[], say its at P2[i0]. Now, we can tell that P2[0], P2[1], …, P2[i0] are all in the subtree rooted at the first child P1[1]. Lets say we are able to reconstruct the tree for this (prove this by inducting on height of subtree say). We have i0+1 nodes that belong to this subtree. They should ideally match completely with P1[1], P1[2], …, P1[i0+1].
Continue to the next child: P1[i0+2]. Find where it is in the array P2[]. Lets say its at i1. We now have that the subtree would be P2[i0+1…i1], which are i1-i0 nodes. Match these with P1[i0+2…i1-1] etc.
In general, we are trying to match one contiguous range of P1 with a contiguous range of P2, and find out how many nodes are there as children of the subtree’s root. Recursively this is done as follows:
int f(int i1, int j1, int i2, int j2) //matches P1[i1...j1] with P2[i2...j2]
if(P1[i1] != P2[j2]) return 0; //root is not defined
if(j1 == i1) return 1; //single node subtree
x = 0
prev1 = i1
prev2 = i2-1
prod = 1
while(prev != j1)
child = P1[prev+1]
i0 = PosInP2[child]
if(i0 < i2 || i0 > j2) return 0; //invalid P1,P2
numnodes = i0-prev2
prod = prod * f(prev1+1, prev+numnodes, prev2+1, prev2+numnodes)
if(prod == 0) return 0;
prev1 += numnodes, prev2 += numnodes
x++
prod = prod * Comb(K, x)
return prod
Note that since K can be as large as N, we should not precompute values of Comb(K, x). However, we can use O(x) computation of Comb(K, x), since total x = N-1 over all nodes of the tree.
Overall time Complexity: O(N)
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here