NeetCode #404LC-545MediumTreesNC Algo100
← Back to All Problems#404 · #545 · Boundary of Binary Tree(二叉树的边界)
📌 Problem Statement & Constraints
Given the root of a binary tree, return its boundary traversal: the root, then the left boundary (excluding leaves) top-down, then all leaves left-to-right, then the right boundary (excluding leaves) bottom-up. Constraints: the number of nodes is in
[1, 10^4].💡 Core Algorithmic Approaches
- Split the traversal into three parts and concatenate them.
- Left boundary: follow the left spine, preferring the left child but falling back to the right, skipping leaves.
- Leaves: a standard DFS collecting leaf values left to right.
- Right boundary: follow the right spine preferring the right child, collect top-down, then reverse.
💻 Benchmark Python3 Implementation
class Solution:
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
def is_leaf(node: Optional[TreeNode]) -> bool:
return not node.left and not node.right
if is_leaf(root):
return [root.val] # a single node is its own boundary
res = [root.val]
# left boundary, top-down, excluding leaves
node = root.left
while node:
if not is_leaf(node):
res.append(node.val)
node = node.left if node.left else node.right
# leaves, left to right
def add_leaves(n: Optional[TreeNode]) -> None:
if not n:
return
if is_leaf(n):
res.append(n.val)
return
add_leaves(n.left)
add_leaves(n.right)
add_leaves(root)
# right boundary, bottom-up, excluding leaves
tmp = []
node = root.right
while node:
if not is_leaf(node):
tmp.append(node.val)
node = node.right if node.right else node.left
res.extend(reversed(tmp))
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited a constant number of times.
💾 Space Complexity
O(h) for the recursion plus O(n) for the result.
⚠️ Interview Pitfalls & Follow-ups
- Including leaves in the left or right boundary: they are collected separately, so both boundary walks must skip them.
- Appending the right boundary top-down: the required order is bottom-up, hence the reversal.
- Double-counting the root: it is added once at the start, and the leaf walk must not re-add it (the single-node case is handled separately).
- Forgetting the fallback to the right child in the left-boundary walk: a left spine may end early while the boundary continues.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.