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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(h)

Three linear passes over disjoint roles.