Binary Tree · DFS
Visual EditorTree Problems

Binary Tree · DFS · BFS

Boundary of Binary Tree

Return the boundary nodes of a binary tree in anti-clockwise order: left boundary → leaves → right boundary (reversed).

DFS · Recursion3-Pass TraversalLeetCode #545 · Medium

Key concepts at a glance — for those who already know the basics.

Problem Statement

Return the values of the boundary nodes of a binary tree in anti-clockwise order starting from the root.

Boundary includes the left boundary (excluding leaves), all leaves from left to right, and the right boundary in reverse (excluding leaves).

Example output: [1, 2, 4, 8, 9, 10, 6, 7, 3]

01 · The definition

Boundary = Left Boundary (top→down, no leaves) + All Leaves (left→right) + Right Boundary (bottom→up, no leaves)

The root is always included. Nodes are collected anti-clockwise so the output "traces the perimeter" of the tree.

02 · The key insight

1
Split the problem into 3 independent passes
Left boundary (top-down, skip leaves) → Leaves (any order, left-to-right) → Right boundary (bottom-up, skip leaves).
2
Left boundary prefers left child; right boundary prefers right child
If the preferred child doesn't exist, go to the other side. Stop before reaching a leaf.
3
Right boundary is appended after recursion (post-order) to reverse it
Anti-clockwise order means the right side must be bottom-up, so we recurse first, append second.

03 · Visual — how the boundary is traced

Root
Left Boundary
Leaves
Right Boundary
Internal (skipped)
1 2 3 4 5 6 7 8 9 10 ① Root ② Left Boundary ↓ ③ Leaves → ④ Right Boundary ↑

Output for this tree: [1, 2, 4, 8, 9, 10, 6, 7, 3] — root, left boundary (2,4), all leaves left-to-right (8,9,10,6), right boundary reversed (7,3).

04 · Code (Python)

class Solution:
def boundaryOfBinaryTree(self, root) -> list:
 
if not root: return []
res = [root.val]
 
def is_leaf(node): # helper
return not node.left and not node.right
 
def left_boundary(node): # top-down, skip leaves
if not node or is_leaf(node): return
res.append(node.val)
if node.left: left_boundary(node.left)
else: left_boundary(node.right)
 
def leaves(node): # collect all leaves L→R
if not node: return
if is_leaf(node):
res.append(node.val); return
leaves(node.left)
leaves(node.right)
 
def right_boundary(node): # bottom-up, skip leaves
if not node or is_leaf(node): return
if node.right: right_boundary(node.right)
else: right_boundary(node.left)
res.append(node.val) # append AFTER recursion → reversed
 
left_boundary(root.left)
leaves(root) # includes root if it's a leaf
right_boundary(root.right)
return res

05 · Dry run — tree [1,2,3,4,5,6,7,8,9,10]

Phase
Node visited
Action
res so far
Init
1 (root)
Always append root
[1]
Left B.
2 → left child
Not leaf → append, go left
[1,2]
Left B.
4 → left child of 2
Not leaf → append, go left
[1,2,4]
Left B.
8 → left child of 4
Is leaf → STOP (leaves phase will add it)
[1,2,4]
Leaves
8
Leaf → append
[1,2,4,8]
Leaves
9
Leaf → append
[1,2,4,8,9]
Leaves
10
Leaf → append
[1,2,4,8,9,10]
Leaves
6
Leaf (no children) → append
[1,2,4,8,9,10,6]
Right B.
7 → right child of 3
Leaf → STOP (append after recursion)
[1,2,4,8,9,10,6]
Right B.
3
Append after right child returns
[1,2,4,8,9,10,6,7,3]

06 · Complexity

Time
O(n)
Each node is visited at most once across the three passes. No node is processed twice.
Space
O(h)
Recursion stack depth equals the tree height h. O(log n) for balanced, O(n) for a skewed tree.

Practice on LeetCode

Try #199 (Right Side View) first — simpler boundary concept to build intuition.

Open on LeetCode ↗