Boundary Traversal of a Binary Tree

Boundary Traversal of a Binary Tree

Print the boundary nodes of a binary tree in anti-clockwise order.

Input format

The first line contains level-order tokens, where N denotes a null node.

Output format

Print anti-clockwise boundary: root, left boundary (excluding leaves), leaves left→right, right boundary bottom-up (excluding leaves).

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.

71 18 76 56 54 82 2 88 N 42 61 N 15 N 89 N N N 38 N 59 80 23 1 11 N N N N N N N N N N 72

18 56 88 38 59 80 23 1 72 11 89 2 76

40 52 60 50 91 19 26 N 51 N N N N 65 90 N N 14 95 87 89 N N N N 5 N 1 39 N N N 74

52 50 51 91 19 14 95 5 74 39 89 90 26 60