On this page
Description
A tree's boundary is its outline, traced counterclockwise from the root. Go down the left edge, along every leaf from left to right, and back up the right edge. It isn't one traversal order. It's three pieces read in different directions and stitched together, with care that the root and the leaves at the ends of each edge appear exactly once.
We'll go from simple to more technical:
- The pattern: the root, the left edge, the leaves, the right edge reversed.
- Where outlining a hierarchy shows up.
- The bugs: double-counted nodes and a right edge read the wrong way.
- The same output from a single DFS with edge flags.
The approach
Collect three pieces separately, then join them. The left edge runs from the root's left child downward. At each step it goes left, or right if there's no left child, and it skips leaves. The leaves come from a separate walk, left to right. The right edge mirrors the left one from the root's right child. It's collected top to bottom, then reversed so the outline comes back up.
| Piece | Read | Nodes |
|---|---|---|
| Root | 8 | |
| Left edge | top to bottom, no leaves | 4 (2 is a leaf, so it's left for the leaf pass) |
| Leaves | left to right | 2, 5, 7, 14 |
| Right edge | bottom to top, no leaves | 15, 12 (at 15 there's no right child, so the walk falls back to 14, a leaf) |
The boundary is 8, 4, 2, 5, 7, 14, 15, 12.
Java
List<Integer> boundaryTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (!isLeaf(root)) result.add(root.val);
addLeftBoundary(root.left, result); // top to bottom, skip leaves
addLeaves(root, result); // left to right, only leaves
addRightBoundary(root.right, result); // collected top to bottom, then reversed to read bottom to top
return result;
}
void addLeftBoundary(TreeNode node, List<Integer> result) {
while (node != null) {
if (!isLeaf(node)) result.add(node.val);
node = (node.left != null) ? node.left : node.right; // prefer left, fall back to right
}
}
// addRightBoundary is the mirror image, preferring right, collecting into a temp list, then reversed
Python
def boundary_traversal(root: TreeNode) -> list[int]:
result = []
if not is_leaf(root):
result.append(root.val)
add_left_boundary(root.left, result) # top to bottom, skip leaves
add_leaves(root, result) # left to right, only leaves
add_right_boundary(root.right, result) # collected top to bottom, then reversed to read bottom to top
return result
def add_left_boundary(node: TreeNode | None, result: list[int]) -> None:
while node is not None:
if not is_leaf(node):
result.append(node.val)
node = node.left if node.left is not None else node.right # prefer left, fall back to right
# add_right_boundary is the mirror image, preferring right, collecting into a temp list, then reversed
Keeping the three pieces separate keeps each one's rules simple: its own direction, and no leaves on the edges.
Where you'll see it
Drawing only the outer outline of a nested layout, such as a tree of UI panels, has the same structure. The pieces of an outline rarely read in one direction, so each needs its own handling. In interviews, this problem mostly tests careful bookkeeping.
Which tool for which job?
| You need | Use |
|---|---|
| The boundary, clearest code | three pieces: left edge, leaves, reversed right edge |
| The boundary in one traversal | DFS carrying "on the left edge" / "on the right edge" flags |
| Only the leaves, left to right | DFS (or an explicit stack), keeping nodes with no children |
| The nodes visible from one side | the level view (next module) - not the same thing |
| Deep trees | iterative edges and an explicit stack for leaves |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Adding edge nodes that are leaves | a leaf appears twice | edges skip leaves; the leaf pass adds them |
| Adding the root when it's a leaf | a single node appears twice | add the root only if it has children |
| Appending the right edge top-down | the outline jumps back to the top | reverse it before appending |
| Using the right subtree when the root has no left | right-side nodes appear as "left edge" | the left edge starts at root.left only |
| Edge walks that stop when a child is missing | the edge ends early | fall back to the other child |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why do the edge walks skip leaves?
Show answer
The leaf pass already adds every leaf. If an edge walk also added the leaf it ends on, that leaf would appear twice, as 2 would above.
2. Why is the right edge reversed before it's appended?
Show answer
The outline goes down the left side, along the bottom and back up the right side. Walking the right edge naturally gives it top to bottom, the opposite of what the outline needs. Reversing it makes the result one continuous loop instead of jumping back to the top.
3. What does a tree with a single node output?
Show answer
Just that node, once. The root is a leaf, so the root step skips it. Both edge walks start from missing children and add nothing. The leaf pass finds the one leaf and adds it.
Key takeaways
- The boundary is three pieces joined: left edge, leaves, right edge.
- The edges skip leaves; the leaf pass adds every leaf exactly once.
- Collect the right edge top to bottom, then reverse it.
- An edge walk falls back to the other child when the preferred one is missing.
- Keeping the pieces separate keeps each one's rules simple.