Post-order traversal of a binary tree
Post-order traversal of a tree is a recursive procedure, where you first the left subtree of a node, then visit its right subtree, and then the node itself:
- Visit the left subtree (
node.left)
- Visit the right subtree (
node.right)
- Visit the current node
Given a binary tree, you are asked to perform a post-order traversal on it.
Input
The input contains space-separated integers representing the values in the nodes of the binary tree. The order of the values is given by traversing from the left to the right subtree every time. A value of 0 means that the node does not exist. It’s guaranteed that the input binary tree is valid.
Output
The program should print the values in the nodes of a binary tree when performing a post-order traversal. All the values should be separated by a space.
Examples
Input | Output |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 9 4 5 2 6 7 3 1 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 5 2 6 7 3 1 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 5 2 6 8 9 7 3 1 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 7 8 5 2 6 3 1 |
Explanation
- Example 1:
.png?table=block&id=0b0397f2-297d-4c60-9cf9-260b4dde3b3d&cache=v2)
- Example 2:
.png?table=block&id=5a5a01d4-a9ed-4456-b4d1-440c54480b9f&cache=v2)
- Example 3:
.png?table=block&id=fc05f8fb-51ae-49b3-a4ff-0b4bf78eee69&cache=v2)
- Example 4:
.png?table=block&id=f66f1408-d6a4-4cf6-bd88-05dd0545d2e1&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB