LeetCode #545 Hard

Boundary of Binary Tree

Return the anticlockwise boundary: root, left edge (top-down), all leaves (left-to-right), right edge (bottom-up) — no duplicates.

treedfs

Open on LeetCode ↗

02

Intuition

The boundary is three separate walks stitched together: slide down the left spine, collect leaves with a normal DFS, slide down the right spine but emit it reversed. The finicky part is exclusion — spine nodes that are leaves belong to the leaf pass only, and the root is emitted once up front.

How to spot this pattern

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.

03

Approach

1

Three collectors

leftBoundary: follow left (else right) from root.left, skipping leaves. leaves: DFS all. rightBoundary: follow right (else left) from root.right, skipping leaves, then reverse.

2

Dedup by role

Root printed first (unless it's a leaf, then the leaf pass owns it); spine passes skip leaves; leaf pass skips nothing — every boundary node has exactly one owner.

3

Stitch

[root] + left + leaves + reversed(right).

04

Solution & live demo

▶1class Solution:
▶2    def boundaryOfBinaryTree(self, root):
▶3        if not root: return []
▶4        def is_leaf(n): return not n.left and not n.right
▶5        if is_leaf(root): return [root.val]
▶6        res = [root.val]
▶7        cur = root.left                       # left spine
▶8        while cur:
▶9            if not is_leaf(cur): res.append(cur.val)
▶10            cur = cur.left if cur.left else cur.right
▶11        def leaves(n):                        # all leaves
▶12            if not n: return
▶13            if is_leaf(n): res.append(n.val); return
▶14            leaves(n.left); leaves(n.right)
▶15        leaves(root)
▶16        right = []
▶17        cur = root.right                      # right spine (reversed)
▶18        while cur:
▶19            if not is_leaf(cur): right.append(cur.val)
▶20            cur = cur.right if cur.right else cur.left
▶21        res += right[::-1]
▶22        return res

05

Common pitfalls

Including leaves while walking the spines

✗ Wrong

while cur:
    res.append(cur.val)
    cur = cur.left if cur.left else cur.right

✓ Right

while 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

✗ Wrong

cur = cur.left

✓ Right

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

✗ Wrong

res = [root.val]
# then spine and leaf passes

✓ Right

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.

06

Edge cases

Root with one subtree

Missing spine contributes nothing; leaves and the existing spine still cover the outline.

Single node

Root is a leaf → emit once, not twice.

07

Complexity

Time

O(n)

Space

O(h)

Three linear passes over disjoint roles.