Recursive traversal of a general tree P66413

Statement

thehtml

Write a program that reads the description of a general tree of natural numbers and prints its postorder traversal.

In this exercise as well as in the rest of exercises of this section, unless the contrary is said the description of a general tree consists of the number of nodes n followed by the pre-order traversal, in which the value of each node is followed by its number of children. This traversal has 2n elements.

(To see an instance with the tree corresponding to the input-output instance, consult the pdf or ps version of this wording.)

To solve this exercixe as well as most of the exercises of this section, you will need to store the tree in a vector. Do it using this code (slightly modified if it is necessary):

typedef vector<int> VE; struct Node { int value; VE children; }; // Reads a tree and stores a part of the vector v starting at the position j. // Modifies the variable j in order to indicates the following free position of v. // Returns the position in c of the root of the read (sub)tree. int tree(int& j, vector<Node>& v) { int a = j; ++j; int f; cin >> v[a].value >> f; v[a].children = VE(f); for (int i = 0; i < f; ++i) v[a].children[i] = tree(j, v); return a; } ... int main() { int n; cin >> n; vector<Node> v(n); int j = 0; tree(j, v); ... }

Each position of the vector stores the value of a node, and the vector with the positions of all its children from the left to the right. The position of the tree root is always 0.

Input

Input consists of the description of a general tree of natural numbers.

Output

Your program must print a line with the postorder traversal of the general tree. Each element must be preceded by a space.

Public test cases

Input

12
7 3  8 0  4 2  3 1  0 1  6 0
5 0  2 4  9 0  1 0  8 0  5 0

Output

 8 6 0 3 5 4 9 1 8 5 2 7

Information

Author: Salvador Roura
Language: English
Translator: Carlos Molina
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++ Python