Rebuilding binary search trees P36853


Statement
 

pdf   zip

html

At the exercise : “” is described a binary search tree with its preorder traversal, which includes a -1 for each leaf. But, in fact, it is not necessary to include the -1’s in the preorder of a search tree to be able to rebuild it.

Write a program that reads a sequence of binary search tree described with their preorder traversal with out -1’s. For each tree, it must write its postorder traversal.

Input

Input consists of a sequence of description of binary trees as it is explained at : “”, with an exception: The -1 corresponding to the leaves are omitted. Suppose that trees are search trees and that its elements are natural numbers.

Output

For each tree of the input, your program must print a line with the postorder traversal of the tree. Each element must be preceded by a space.

Public test cases
  • Input

    10
    180 155 60 80 170 300 240 400 310 340
    
    3
    30 20 10
    

    Output

     80 60 170 155 240 340 310 400 300 180
     10 20 30
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions