Leetcode 545. Boundary of Binary Tree

Let's understand what we're being asked to do. We have a binary tree, and we need to return its boundary in a specific order.

The boundary consists of three parts:

1. Left boundary (top-down): All nodes on the leftmost path, excluding leaf nodes
2. All leaves (left-to-right): Every leaf node in the tree, traversed from left to right
3. Right boundary (bottom-up): All nodes on the rightmost path, excluding leaf nodes, in reverse order

For example, given a tree with root 1, left child 2, right child 3, where 2 has children 4 and 5, and 3 has children 6 and 7:

• Left boundary: [1, 2] (going down the left side, excluding leaf 4)
• Leaves: [4, 5, 6, 7] (all leaf nodes left-to-right)
• Right boundary: [3] (going up from bottom, excluding leaf 7)
• Final result: [1, 2, 4, 5, 6, 7, 3]

Important constraints: The root is always included (unless it's a leaf). We must avoid duplicates - a node can only appear once in the boundary.

Edge cases to consider: What if the tree has only one node (the root is a leaf)? What if the tree is completely skewed to one side? What if a node appears in multiple categories (e.g., root is both left and right boundary)?

The boundary forms a counterclockwise traversal around the tree's perimeter. We're essentially walking around the outside edge of the tree.

The key insight is that we need to partition nodes into three distinct groups: left boundary nodes (excluding leaves), leaf nodes, and right boundary nodes (excluding leaves). Each group requires a different traversal strategy.

By separating the problem into three independent traversals, we can handle each part with its own logic:

• Left boundary: Keep going left (or right if no left child exists) until we hit a leaf
• Leaves: Standard tree traversal (DFS or BFS) to collect all leaf nodes
• Right boundary: Keep going right (or left if no right child exists), then reverse the order

This decomposition makes the problem much more manageable than trying to do everything in one pass.

Imagine walking around the perimeter of a building. You'd walk down the left side, across the bottom, then back up the right side.

For a tree, the 'left side' is the leftmost path (always preferring left children), the 'bottom' is all the leaves, and the 'right side' is the rightmost path (always preferring right children).

The tricky part is avoiding duplicates: if a node is on the left boundary, it shouldn't also be counted as a leaf. If the root is a leaf, it should only appear once. This requires careful checking of node types before adding them to our result.

The optimal approach uses three separate traversals to collect the boundary nodes. First, traverse the left boundary by always going left (or right if no left child), stopping before leaves. Second, perform a DFS to collect all leaf nodes in left-to-right order. Third, traverse the right boundary by always going right (or left if no right child), then reverse this list. Finally, concatenate all three parts while carefully handling the root node to avoid duplicates. This ensures each node appears exactly once in the correct order.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def boundary_of_binary_tree(root):
    """
    Return the boundary of a binary tree in anti-clockwise order.
    Boundary includes: left boundary (top-down), leaves (left-to-right), right boundary (bottom-up).
    """
    if not root:
        return []
    
    # Special case: single node (root is both boundary and leaf)
    if not root.left and not root.right:
        return [root.val]
    
    result = []
    
    # Add root (always part of boundary unless it's a leaf)
    result.append(root.val)
    
    # Step 1: Collect left boundary (top-down, excluding leaves)
    def get_left_boundary(node):
        if not node or (not node.left and not node.right):
            return
        
        result.append(node.val)
        
        # Prefer left child, go right only if no left
        if node.left:
            get_left_boundary(node.left)
        else:
            get_left_boundary(node.right)
    
    # Step 2: Collect all leaves (left-to-right using DFS)
    def get_leaves(node):
        if not node:
            return
        
        # If it's a leaf, add it
        if not node.left and not node.right:
            result.append(node.val)
            return
        
        # Traverse left subtree first, then right (for left-to-right order)
        get_leaves(node.left)
        get_leaves(node.right)
    
    # Step 3: Collect right boundary (bottom-up, excluding leaves)
    def get_right_boundary(node):
        if not node or (not node.left and not node.right):
            return
        
        # Prefer right child, go left only if no right
        if node.right:
            get_right_boundary(node.right)
        else:
            get_right_boundary(node.left)
        
        # Add after recursion for bottom-up order
        result.append(node.val)
    
    # Execute the three traversals
    get_left_boundary(root.left)
    get_leaves(root)
    get_right_boundary(root.right)
    
    return result

• Three-phase tree traversal decomposition: Break complex boundary problems into three independent traversals (left boundary top-down, leaves left-to-right via inorder, right boundary bottom-up) - this separation of concerns makes the logic manageable and prevents tangled conditionals that arise from trying to handle everything in one pass.
• Boundary definition precision: The left boundary follows 'always go left, if no left then right' while right boundary follows 'always go right, if no right then left' - understanding that boundaries are path-based not subtree-based is critical, as each boundary is a single chain from root toward leaves, not all leftmost/rightmost nodes.
• Leaf node deduplication strategy: Since leaves appear in all three traversal categories, explicitly exclude leaf nodes (nodes with no children) from left and right boundary collections, then gather all leaves separately via a complete tree traversal - this prevents duplicates without needing hash sets or post-processing.
• Reverse collection for bottom-up ordering: For the right boundary, collect nodes during a top-down traversal but reverse the collection before appending to the result - this is more efficient than recursively building bottom-up and avoids stack overflow risks on skewed trees.
• Root node special handling: The root is part of the boundary but not a leaf by definition of this problem - handle it separately at the start to avoid complex conditionals about whether root appears in left boundary, right boundary, or both (especially critical for single-node trees).
• Skewed tree edge cases: Test with completely left-skewed and right-skewed trees where the boundary path degenerates - in these cases, the left or right boundary becomes the entire path, and proper leaf exclusion prevents nodes from appearing twice in your output.