Binary Tree Postorder Traversal
Traverse a binary tree in postorder (left, right, root), iteratively and recursively.
Input format
The first line contains level-order tokens, where N denotes a null node.
Output format
Print the postorder traversal of the tree, space-separated.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
9 24 8 79 40 N N 51 21 N N 43Expected output
43 51 21 79 40 24 8 9Example 2
Input
25 14 4 50 97 N 20 N 68 N 29 72 33 39 N 16 5 N N 82 N N N N N 69 N 70 N 45Expected output
39 68 50 16 45 69 5 29 97 14 72 70 82 33 20 4 25