LeetCode 545: Boundary of Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 545: Boundary of Binary Tree?

In LeetCode 545: Boundary of Binary Tree, you’re given the root of a binary tree, and your task is to return an array of node values representing the boundary in clockwise order: the root, all left boundary nodes (excluding leaves if already counted), all leaves from left to right, and all right boundary nodes (excluding leaves if already counted), in reverse order. For example, with a tree [1, 2, 3, 4, 5, null, null, 6, 7, null, 8], the boundary is [1, 2, 4, 6, 7, 8, 5, 3]. This problem builds on LeetCode 94: Binary Tree Inorder Traversal for traversal techniques and introduces boundary-specific logic.

Problem Statement

• Input: root (TreeNode)—root of a binary tree.
• Output: List[int]—node values on the boundary in clockwise order.
• Rules: Include root, left boundary (top-down), leaves (left-to-right), right boundary (bottom-up); avoid duplicates.

Constraints

• Number of nodes: 1 to 10⁴.
• Node values: -10³ to 10³.

Examples

• Input: root = [1,2,3,4,5,null,null,6,7,null,8]
• Output: [1,2,4,6,7,8,5,3]
• Tree:
``` 1 / \ 2 3 / \ 4 5 / \ 6 7 \ 8 ```
• Boundary: Root (1), Left (2, 4), Leaves (6, 7, 8), Right (5, 3).
• Input: root = [1,null,2,3,4]
• Output: [1,2,3,4]
• Tree:
``` 1 \ 2 / \ 3 4 ```
• Boundary: Root (1), Right (2), Leaves (3, 4).
• Input: root = [1]
• Output: [1]
• Single node.

Understanding the Problem: Tracing the Boundary

To solve LeetCode 545: Boundary of Binary Tree in Python, we need to collect node values along the tree’s boundary in clockwise order: root, left edge (excluding leaf overlaps), bottom leaves, and right edge (bottom-up, excluding overlaps). A naive approach might traverse the tree multiple times, but with up to 10⁴ nodes, we can optimize with a single-pass strategy or layered traversal. The boundary splits into distinct parts, requiring careful handling to avoid duplicates. We’ll explore:

• Best Solution (DFS with Three-Pass Approach): O(n) time, O(h) space (h = height)—efficient and clear.
• Alternative Solution (BFS with Level Tracking): O(n) time, O(w) space (w = width)—thorough but bulkier.

Let’s dive into the DFS solution with a friendly breakdown!

Best Solution: DFS with Three-Pass Approach

Why DFS Wins

The DFS with three-pass approach is the best for LeetCode 545 because it efficiently traverses the tree in O(n) time and O(h) space (recursion stack), splitting the boundary into three logical parts—left boundary, leaves, and right boundary—using tailored DFS methods to collect nodes in order while avoiding duplicates. It’s like sketching the tree’s outline with three careful strokes!

How It Works

Think of this as a tree-outline artist:

• Step 1: Left Boundary:
• DFS down left children, add nodes until leaf, exclude leaf if it’s a boundary leaf.
• Step 2: Leaves:
• DFS to collect all leaves (no children), left-to-right.
• Step 3: Right Boundary:
• DFS down right children, add nodes bottom-up, exclude leaf if already counted.
• Step 4: Combine:
• Root + left + leaves + right (adjusted for duplicates).
• Why It Works:
• Three passes target specific boundary parts.
• Flags and checks prevent overlap.

It’s like a tree-boundary tracer!

Step-by-Step Example

Example: root = [1, 2, 3, 4, 5, null, null, 6, 7, null, 8]

• Init: result = [].
• Step 1: Left Boundary:
• Start at 1, add 1 (root).
• Left (2), add 2, Left (4), add 4 (not leaf yet).
• Stop at 6 (leaf, exclude).
• Left = [1, 2, 4].
• Step 2: Leaves:
• DFS: 6 (leaf), 7 (leaf), 8 (leaf), 5 (leaf if no right child counted).
• Leaves = [6, 7, 8, 5].
• Step 3: Right Boundary:
• Right (3), add 3 (bottom-up).
• Right (5), add 5 (but leaf, exclude if counted), stop at 8 (leaf).
• Right = [3] (5 already in leaves).
• Step 4: Combine:
• Result = [1, 2, 4, 6, 7, 8, 5, 3].
• Result: [1, 2, 4, 6, 7, 8, 5, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        # Step 1: Initialize result with root
        result = [root.val] if root.left or root.right else [root.val]

        # Step 2: Left boundary (exclude leaves if counted)
        def left_boundary(node):
            if not node or (not node.left and not node.right):
                return
            result.append(node.val)
            if node.left:
                left_boundary(node.left)
            else:
                left_boundary(node.right)

        # Step 3: Collect leaves
        def leaves(node):
            if not node:
                return
            if not node.left and not node.right:
                result.append(node.val)
                return
            leaves(node.left)
            leaves(node.right)

        # Step 4: Right boundary (bottom-up, exclude leaves if counted)
        def right_boundary(node):
            if not node or (not node.left and not node.right):
                return
            if node.right:
                right_boundary(node.right)
            else:
                right_boundary(node.left)
            result.append(node.val)

        # Step 5: Execute three passes
        if root.left:
            left_boundary(root.left)
        leaves(root)
        if root.right:
            right_boundary(root.right)

        return result

• Lines 12-13: Handle empty or single-node tree.
• Lines 16-23: Left DFS: Add non-leaf nodes top-down.
• Lines 26-33: Leaf DFS: Collect leaves left-to-right.
• Lines 36-43: Right DFS: Add non-leaf nodes bottom-up.
• Lines 46-50: Run passes, skip if no left/right subtree.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a tree-edge painter!

Alternative Solution: BFS with Level Tracking

Why an Alternative Approach?

The BFS with level tracking solution uses breadth-first search to traverse level-by-level, identifying boundary nodes (leftmost, rightmost, leaves) in O(n) time and O(w) space (w = max width). It’s thorough but requires extra bookkeeping, making it a good alternative for BFS fans or when level-order intuition is preferred.

How It Works

Picture this as a tree-level scanner:

• Step 1: BFS with level info.
• Step 2: Track leftmost, rightmost, and leaves per level.
• Step 3: Combine boundary nodes in order.

It’s like a tree-level boundary mapper!

Step-by-Step Example

Example: root = [1, 2, 3, 4, 5]

• BFS:
• Level 0: [1], left = 1, right = 1.
• Level 1: [2, 3], left = 2, right = 3.
• Level 2: [4, 5], leaves = [4, 5].
• Combine: [1, 2, 4, 5, 3].
• Result: [1, 2, 4, 5, 3].

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        if not root.left and not root.right:
            return [root.val]

        # Step 1: BFS with level tracking
        queue = deque([(root, 0)])
        levels = {}
        while queue:
            node, level = queue.popleft()
            if level not in levels:
                levels[level] = {'left': [], 'right': [], 'leaves': []}
            if not node.left and not node.right:
                levels[level]['leaves'].append(node.val)
            else:
                if not levels[level]['left']:
                    levels[level]['left'].append(node.val)
                levels[level]['right'].append(node.val)
            if node.left:
                queue.append((node.left, level + 1))
            if node.right:
                queue.append((node.right, level + 1))

        # Step 2: Build boundary
        result = [root.val]
        for level in sorted(levels.keys()):
            if level > 0:  # Exclude root level for left
                result.extend(levels[level]['left'])
            result.extend(levels[level]['leaves'])
            if levels[level]['right'] and levels[level]['right'][-1] not in levels[level]['leaves']:
                result.append(levels[level]['right'][-1])

        return result

• Lines 11-24: BFS tracks leftmost, rightmost, leaves per level.
• Lines 27-33: Combine boundary in order, avoid duplicates.
• Time Complexity: O(n)—single BFS pass.
• Space Complexity: O(w)—queue and level storage.

It’s a BFS boundary tracker!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n), O(h), clear and efficient.
• Cons: Three-pass logic.
• BFS (Alternative):
• Pros: O(n), O(w), level-based.
• Cons: More space, bookkeeping.

DFS wins for simplicity and space!

Additional Examples and Edge Cases

• [1]: [1].
• [1, 2]: [1, 2].
• [1, null, 2, null, 3]: [1, 2, 3].

DFS handles them all!

Complexity Recap

• DFS: Time O(n), Space O(h).
• BFS: Time O(n), Space O(w).

DFS’s the elegance champ!

Key Takeaways

• DFS: Three-pass tracing—learn at Python Basics!
• BFS: Level-by-level scan.
• Trees: Boundaries are fun.
• Python: DFS or BFS, your pick!

Final Thoughts: Trace That Boundary!

LeetCode 545: Boundary of Binary Tree in Python is a delightful tree challenge. DFS with three-pass approach is your fast track, while BFS offers a level-based twist. Want more? Try LeetCode 94: Inorder Traversal or LeetCode 199: Right Side View. Ready to outline? Head to Solve LeetCode 545 on LeetCode and trace that boundary today!