Trees - Recursive traversal P98436


Statement
 

pdf   zip

thehtml

Write a program that reads the description of a natural binary tree and prints its postorder and inorder traversals.

The description of a tree consists of its traversal in preorder, which includes the leaves marked with a -1.

Have a look on the PDF file.

Input

Input consists of the description of a natural binary tree.

Output

Your program must print two lines, with the postorder and inorder traversals of the tree. Follow the format in the samples.

Public test cases
  • Input

    3 0 7 -1 4 -1 -1 2 -1 -1 5 4 -1 -1 7 6 -1 1 -1 -1 -1
    

    Output

    pos: 4 7 2 0 4 1 6 7 5 3
    ino: 7 4 0 2 3 4 5 6 1 7
    
  • Information
    Author
    Jordi Petit i Salvador Roura
    Language
    English
    Translator
    Jordi Petit
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python