⚡Flashcard Drill➔
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

  1. Split the traversal into three parts and concatenate them.
  2. Left boundary: follow the left spine, preferring the left child but falling back to the right, skipping leaves.
  3. Leaves: a standard DFS collecting leaf values left to right.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems