Boundary Traversal of Binary Tree

Boundary Traversal asks you to walk the outline of a binary tree — the silhouette you would trace if you ran a finger anti-clockwise around the whole shape. It looks fiddly, but it breaks cleanly into three independent passes, and that decomposition is the whole lesson.

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

The slow way first

You could try to compute the outline in one clever traversal, tracking whether each node is "leftmost," "a leaf," or "rightmost." It is doable, but the bookkeeping is brutal: a node can be on the left edge and a leaf, the root counts but the reversed right edge must not re-add it, and a one-sided spine quietly breaks the naive "go left, else go right" rule. Most people who try the all-in-one version get a duplicate or a missing node.

The question to ask: can I split this into pieces that do not overlap? If I handle the left edge, the leaves, and the right edge separately — each skipping what the others own — every node lands in exactly one pass.

The idea: three clean passes

Split the boundary into three lists and concatenate them:

1. Left boundary, top-down, excluding leaves (the leaf pass will grab those).
2. All leaves, left to right.
3. Right boundary, top-down but collected then reversed, excluding leaves.

The root is prepended once (unless the whole tree is a single leaf). Because each pass skips leaves, and the leaf pass is the only one that adds them, no node is counted twice.

The key insight: leaves are the seam. By excluding them from the two edge passes and letting one dedicated pass own them, the three parts fit together with no overlap and no gap.

Walk through it

Step through the animation. First the root 1 is added. Pass one walks down the left edge and adds 2, stopping when it hits the leaf 4. Pass two sweeps the bottom row left to right — 4, 5, 6, 7. Pass three walks the right edge, collecting 3, then reverses that list before appending. The growing out list at the bottom shows the answer assembling: [1, 2, 4, 5, 6, 7, 3].

Pseudocode

if tree is empty: return []
out = [root]  unless root is itself a leaf
 
add_left_boundary:   # top-down, skip leaves
    node = root.left
    while node:
        if node is not a leaf: append node
        node = node.left if it exists else node.right
 
add_leaves:          # recurse, append only leaves, left to right
    if node is a leaf: append node
    else: recurse left, then recurse right
 
add_right_boundary:  # collect top-down, then reverse
    node = root.right
    while node:
        if node is not a leaf: collect node
        node = node.right if it exists else node.left
    append the collected list reversed
 
return out

The Python solution

def boundary(root):
    if not root: return []
    out = [] if is_leaf(root) else [root.val]
    add_left_boundary(root, out)
    add_leaves(root, out)
    add_right_boundary(root, out)
    return out
 
def add_left_boundary(root, out):
    node = root.left
    while node:
        if not is_leaf(node): out.append(node.val)
        node = node.left or node.right
 
def add_leaves(node, out):
    if is_leaf(node): out.append(node.val); return
    if node.left:  add_leaves(node.left, out)
    if node.right: add_leaves(node.right, out)
 
def add_right_boundary(root, out):
    node, right = root.right, []
    while node:
        if not is_leaf(node): right.append(node.val)
        node = node.right or node.left
    out += reversed(right)

• is_leaf(node) is not node.left and not node.right — a node with no children.
• The root is added first, unless it is a leaf (a one-node tree returns just that node, with no double-counting).
• add_left_boundary walks down, preferring the left child but falling back to the right (node.left or node.right) so a one-sided spine still descends.
• Inside each edge pass, if not is_leaf(node) is what excludes leaves — that is the rule that prevents overlap with the leaf pass.
• add_leaves recurses left-then-right, so leaves are appended in left-to-right order.
• add_right_boundary collects into a separate right list and appends it reversed, turning a top-down walk into the bottom-up order the outline needs.

Complexity

We touch every node a constant number of times, so the work is O(n). The extra space is the recursion stack for the leaf pass plus the small right list — both bounded by the tree height h, so O(h).

When this pattern shows up

Practice