Boundary Traversal of Binary Tree
WHAT IT SAYS
List the boundary of a binary tree anticlockwise: the root, the left edge going down, all the leaves left-to-right, and the right edge going up.
WHAT IT'S REALLY ASKING
"There is no single traversal that produces this order — stop looking for one. The boundary is three DIFFERENT walks stitched together, each trivial alone, and the entire difficulty of the problem lives at the seams: the corners where two walks would both claim the same node."
Classify every node during one grand traversal
O(n) time, but the ordering logic is where it diesDo a single DFS carrying flags — 'am I on the left boundary?', 'am I on the right boundary?', 'am I a leaf?' — and emit nodes whose flags say boundary. Then fight with the ordering, because DFS order is not boundary order.
WHERE THE WORK IS WASTED — The waste is not compute — it is that one traversal is being asked to produce three different orders at once. The left edge wants top-down, the right edge wants BOTTOM-UP, and the leaves want left-to-right; no single visit order delivers all three, so the flag-based walk ends with sorting or buffer-juggling to repair the order it mangled. Meanwhile the flag logic itself is a bug farm: a node can be simultaneously a leaf AND the end of the left edge, and the single-pass version either prints it twice or writes special cases inline where they are hardest to see.
Three disjoint walks, and the corners decide who owns what.
Define the three parts precisely and the algorithm assembles itself. Part one: the left edge — start at the root's left child, and at each step go left if you can, else go right; stop before any leaf. Part two: every leaf, in left-to-right order — one plain DFS that emits only childless nodes. Part three: the right edge — same walk as the left edge but mirrored, and emitted in reverse because the anticlockwise tour comes UP that side. The correctness question is entirely about double-counting, so resolve ownership explicitly. Leaves are claimed by part two — therefore parts one and three must EXCLUDE leaves, or the bottom-left and bottom-right corner nodes get printed twice. The root is claimed by nobody's walk — print it first, separately, or the two edge walks both start from it. Get those two ownership rules right and the three parts are provably disjoint and provably cover the boundary; get either wrong and the output is subtly duplicated in a way tests catch and eyes don't. The right edge's reversal deserves one more sentence: you cannot walk a downward-pointing tree upward, so you collect top-down into a buffer and emit it backwards. That is not a hack — it is the honest admission that the desired order and the walkable order differ, handled at the output, not by contorting the walk. Edge cases fall out of ownership too: a single-node tree is a root that is also a leaf — print it once. A root with only a left subtree has NO right edge at all, and the walk-definition handles that by producing an empty part rather than by a special case.
Root, then left edge, then leaves, then reversed right edge
O(n) time — the leaf DFS dominates — O(h) stack space plus the right-edge bufferEmit the root (if it is not itself a leaf, or handle that case once). Walk the left edge from root.left, emitting each non-leaf. DFS the whole tree emitting leaves in order. Walk the right edge from root.right into a buffer, skipping leaves, and emit the buffer reversed. Concatenate the four pieces.
Stitch Natural Walks at the Seams
YOU'LL SEE IT AGAIN WHEN
- The required output order is not producible by any single standard traversal — it changes direction or regime partway through.
- The output splits into segments, each of which IS some trivial walk's natural order (an edge chase, a leaf scan, a reversed collection).
- Corner elements plausibly belong to two segments, so correctness hinges on explicit ownership rules, not on the walks themselves.