Recursive traversal of a general tree P66413


pdf   zip


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 consists of the description of a general tree of natural numbers.


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

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


     8 6 0 3 5 4 9 1 8 5 2 7
  • Information
    Salvador Roura
    Carlos Molina
    Original language
    Other languages
    Official solutions
    User solutions
    C++ Python