Boundary of Binary Tree
Boundary of Binary Tree: return the anticlockwise boundary: root, left edge (top-down), all leaves (left-to-right), right edge (bottom-up) — no duplicates.
- 1 <= number of nodes <= 10⁴
- -1000 <= node value <= 1000
- Boundary is anticlockwise and each node appears once
Intuition
The boundary of binary tree is its outline traversed anticlockwise: the root, then the left edge from top to bottom, then all the leaves left to right, then the right edge from bottom to top. The algorithm itself is three straightforward walks — the difficulty is entirely in making sure no node appears twice.
The overlaps are real. The lowest node of the left edge is often a leaf, so it belongs to both the edge walk and the leaf walk. The root may itself be a leaf in a single-node tree. Without a clear rule, boundary nodes get emitted two or three times.
The rule that resolves it cleanly is to give every boundary node exactly one owner:
- The root is emitted first and belongs to nobody else.
- The edge walks skip leaves entirely — leaves are owned by the leaf pass.
- The leaf pass collects every leaf, wherever it sits.
One more subtlety: the left edge follows left when it exists and otherwise falls back to right, because the outline of the tree does not stop where the left children stop. The right edge mirrors that.
Finally the right edge must be reversed, since it is collected top-down but the anticlockwise outline reads it bottom-up. Stitch the four pieces together and the boundary is complete.
The boundary of binary tree is three disjoint pieces stitched together: left spine top-down, all leaves left-to-right, right spine bottom-up. The is_leaf exclusion in both spine walks is what stops nodes being counted twice, since a spine can end in a leaf that the middle pass will also collect.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Emit the root first, then never again
The root opens the output and is excluded from all three walks. If the root is itself a leaf — a single-node tree — emit it once and stop, or the leaf pass will duplicate it.
Walk the left edge, skipping leaves
From root.left, follow left when it exists and right otherwise, appending each node unless it is a leaf. The fallback to right matters: the outline continues even where left children run out.
Collect every leaf left to right
Run a full DFS and append each node with no children. This pass owns all leaves, including those sitting at the bottom of either edge, which is what keeps the edge walks free of duplicates.
Walk the right edge, then reverse it
From root.right, follow right when it exists and left otherwise, again skipping leaves. Reverse the collected list — it is gathered top-down but the anticlockwise outline needs it bottom-up.
Stitch the four pieces
Concatenate root, left edge, leaves, reversed right edge. Because each node has exactly one owner, no deduplication step is needed — the ownership rule does that work up front.
Cost of the three walks
The edge walks are O(h) each and the leaf collection is O(n), giving O(n) time overall. Space is O(n) for the output plus O(h) for the traversal stack.
Solution & live demo
Common pitfalls
Including leaves while walking the spines
while cur:
res.append(cur.val)
cur = cur.left if cur.left else cur.rightwhile cur:
if not is_leaf(cur): res.append(cur.val)
cur = ...The leaf pass collects every leaf, including the ones terminating each spine. Without the exclusion those nodes appear twice in the output.
Following only the left child down the left spine
cur = cur.left
cur = cur.left if cur.left else cur.right
The left boundary continues through a right child when no left child exists — the spine is the leftmost path, not the chain of left pointers. Stopping early truncates the boundary.
Not special-casing a single-node tree
res = [root.val] # then spine and leaf passes
if is_leaf(root): return [root.val]
A lone root is itself a leaf, so the leaf pass adds it a second time. The guard returns before the three-part assembly can duplicate it.
Edge cases
Missing spine contributes nothing; leaves and the existing spine still cover the outline.
Root is a leaf → emit once, not twice.