Boundary of Binary Tree

Given the root of a binary tree, return the values of its boundary in anti-clockwise order, starting from the root.

The boundary is the concatenation of: the root; the left boundary (top-down, excluding leaves); the leaves (left to right); and the right boundary (bottom-up, excluding leaves). The left boundary is the path from the root's left child taking left when possible else right; the right boundary is symmetric. Each node appears once, and if the root is a leaf the boundary is just the root.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Assemble four parts: root, left boundary (top-down), leaves (left to right), right boundary (bottom-up).

Exclude leaves from the two side boundaries so they aren't counted twice.

Collect the right boundary top-down and reverse it, or append it post-order in recursion.

Common doubts

Skip leaves in the left and right boundary walks; the leaf pass covers them exactly once.

The anti-clockwise loop goes up the right side, but you naturally collect it top-down, so it must be reversed (or appended post-order).

The root is a leaf, so the boundary is just [root.val] — handle this before the side passes.

Interview follow-ups

· What an interviewer asks next.

It follows the right child instead, so the 'leftmost path' bends right when it must, keeping the boundary connected.

Reverse the roles: right boundary top-down, leaves right-to-left, left boundary bottom-up.

Fun facts

The recursive version gets bottom-up order for the right boundary for free by appending after the recursive call.
Boundary traversal is a favorite for testing careful handling of the leaf/edge overlap.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [1, null, 2, 3, 4]
Output: [1, 3, 4, 2]
Root 1; no non-leaf left boundary; leaves 3, 4; right boundary (2) bottom-up.

Example 2

Input: root = [1, 2, 3, 4, 5, 6, null, null, null, 7, 8, 9, 10]
Output: [1, 2, 4, 7, 8, 9, 10, 6, 3]
Root; left boundary 2; leaves 4, 7, 8, 9, 10; right boundary 6, 3 bottom-up.

Constraints

- The number of nodes is in the range [1, 10^4] - -1000 <= Node.val <= 1000

The boundary is four pieces glued together: root, left boundary (top-down), leaves (left to right), and right boundary (bottom-up). The care is in avoiding duplicates — the left and right boundaries exclude leaves (which the leaf pass covers) — and in reversing the right boundary so the whole thing reads anti-clockwise.

Prerequisites

Before you start

· Concepts used directly in the solution.

Leaf detection. A node with no children ends the leaf pass and is excluded from the side boundaries.

Directional descent. Left boundary prefers left children; right boundary prefers right children.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Order?”

Anti-clockwise: root, left side down, leaves left-to-right, right side up.

“Are leaves counted twice?”

No — the side boundaries exclude leaves; leaves are listed once in the leaf pass.

The ideal opening — say it like this

I output the root, then the left boundary top-down excluding leaves, then all leaves left to right, then the right boundary bottom-up excluding leaves.

The two side passes skip leaves to avoid double-counting, and the right side is reversed so the traversal is anti-clockwise.

Understand the problem

Worked example — tree [1, 2, 3, 4, 5, 6, null, null, null, 7, 8, 9, 10]

root: 1
left boundary (from 2, skip leaves): 2
leaves (L->R): 4, 7, 8, 9, 10
right boundary (from 3, skip leaves), reversed: 6, 3
boundary: [1, 2, 4, 7, 8, 9, 10, 6, 3]

Key observations

1Aha

Four passes, one rule each

Root, left (top-down), leaves (L-R), right (bottom-up) — the anti-clockwise loop.

2Aha

Exclude leaves from the sides

Leaves belong only to the leaf pass; skip them in the side boundaries to avoid duplicates.

3Aha

Reverse the right boundary

Collected top-down, it must be reversed to complete the anti-clockwise order.

Brute force vs optimal

	Iterative side passes	Recursive side passes
Idea	While-loops for left/right, DFS for leaves	Pre-order left, post-order right, DFS leaves
Time	O(n)	O(n)
Space	O(n)	O(height)

Same four-part decomposition; the recursion appends the right boundary post-order to get bottom-up for free. Full code is in the Approaches selector below.

Summary

Key takeaway

Concatenate root + left boundary (top-down, no leaves) + leaves (L→R) + right boundary (bottom-up, no leaves). Exclude leaves from the sides and reverse the right side. O(n).

res = [root]
walk left edge (skip leaves) top-down
collect all leaves left to right
walk right edge (skip leaves), reverse, append