Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 545. Boundary of Binary Tree

Return the boundary of a binary tree: list nodes on the left boundary top-down (excluding leaves), then all leaves left-to-right, then the right boundary bottom-up (excluding leaves), avoiding duplicates. The challenge is to traverse and partition nodes correctly (including edge cases like single-node or skewed trees) while preserving the required order.

Asked at:

Amazon

DESCRIPTION

Input:

root = [1,2,3,4,5,6,7]

Output:

[1,2,4,5,6,7,3]

Explanation: Left boundary: [1,2] (excluding leaf 4). Leaves: [4,5,6,7]. Right boundary: [3] (excluding leaf 7). Combined: [1,2,4,5,6,7,3]

Constraints:

The number of nodes in the tree is in the range [1, 10^4]
-1000 <= Node.val <= 1000
The root is never null
All node values are unique

Understanding the Problem

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:

Left boundary (top-down): All nodes on the leftmost path, excluding leaf nodes
All leaves (left-to-right): Every leaf node in the tree, traversed from left to right
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)?

Building Intuition

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.

Common Mistakes

Forgetting to exclude leaf nodes from the left and right boundaries - leaves should only appear in the middle section, not in the boundary paths

Not handling the root node correctly when it's a leaf - it should appear exactly once in the result, not be excluded

Reversing the entire result instead of just the right boundary - only the right boundary needs to be reversed (bottom-up), not the leaves or left boundary

Including internal nodes in the leaves collection - a leaf must have no children (both left and right are null)

Not handling skewed trees correctly - when there's no left child, the left boundary should continue with the right child, and vice versa for the right boundary

Optimal Solution

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.

Visualization

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

Start boundary traversal

0 / 34

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each node at most once across all three traversals (left boundary, leaves collection, right boundary), resulting in linear time complexity where n is the number of nodes

Space Complexity: O(n) In the worst case, we store all nodes in our result array. Additionally, the recursive DFS for collecting leaves uses O(h) stack space where h is the tree height, which can be O(n) for a skewed tree

What We've Learned

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.

Test Your Understanding

Why is tree the right data structure for this problem?

tree provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early October, 2025

Amazon

Mid-level

Mid September, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More