Binary Tree Inorder Traversal
Traverse a binary tree in inorder (left, root, right), iteratively and recursively.
Input format
The first line contains level-order tokens, where N denotes a null node.
Output format
Print the inorder 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
55 20 38 22 93 44 61 N N 34 26 32 78 76 52 N N N 7 N N N N N N N 89 31Expected output
22 20 34 93 26 31 7 55 32 44 78 38 76 61 52 89Example 2
Input
6 85 N N 3Expected output
85 3 6