Boundary Traversal of Binary Tree
hardTrees & BST II+40 XPTime limit 2s
Trace the outline of a binary tree anticlockwise, starting at the root, and print every node on it exactly once. The outline has four parts, in this order:
- The root.
- The left boundary, top to bottom: start at the root's left child; from each node move to its left child if it has one, otherwise to its right child; stop when you reach a leaf. Leaves on this path are not printed here. (If the root has no left child, this part is empty.)
- All leaves, from left to right (the root itself does not count as a leaf).
- The right boundary, bottom to top: the mirror of part 2 — start at the root's right child, prefer the right child, then the left; again without leaves. (Empty if the root has no right child.)
Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is
3
/ \
9 20
/ \
15 7
Input: one tree.
Output: the boundary values on one line, or empty for an empty tree.
Constraints: 0 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: handle the three parts separately and glue them. The left and right boundaries are simple loops; the leaves come from any left-before-right traversal (preorder or inorder). The tricky cases are a root with only one child, and a boundary that ends in a leaf — that leaf must be printed once, in the leaves part.
Sample input 1
1 2 3 4 5 6 7 null null 8 9
Sample output 1
1 2 4 8 9 6 7 3
Sample input 2
1 null 2 3 4
Sample output 2
1 3 4 2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).