Problem Description

You need to find the boundary of a binary tree, which consists of four parts concatenated in order:

1. The root node
2. The left boundary (excluding leaves)
3. All leaf nodes from left to right
4. The right boundary in reverse order (excluding leaves)

Left Boundary Rules:

• Start with the root's left child (if it exists)
• For each node in the left boundary:
  • If it has a left child, the left child is the next boundary node
  • If it has no left child but has a right child, the right child is the next boundary node
  • Stop when reaching a leaf (the leaf is not part of the left boundary)

Right Boundary Rules:

• Similar to left boundary but mirror image - start with root's right child
• Prefer right children over left children
• The rightmost leaf is not included in the right boundary
• The final right boundary values should be reversed when added to the result

Leaves:

• Nodes with no children
• Collected from left to right across the entire tree
• The root is never considered a leaf

Special Cases:

• If the root has no left child, the left boundary is empty
• If the root has no right child, the right boundary is empty
• If the tree has only one node (the root), return just that node's value

Given the root of a binary tree, return a list containing the values of all nodes on the boundary, following the order: root → left boundary → leaves → reversed right boundary.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: We arrive at DFS as the recommended approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this binary tree problem.

This makes perfect sense for the Boundary of Binary Tree problem because:

1. We need to traverse down the left boundary following a specific path (always preferring left child, then right child if no left exists)
2. We need to collect all leaf nodes in left-to-right order, which requires visiting every node in the tree
3. We need to traverse down the right boundary following a specific path (always preferring right child, then left child if no right exists)
4. DFS allows us to control the traversal pattern precisely - we can modify our traversal behavior based on whether we're collecting left boundary, leaves, or right boundary nodes

The solution uses DFS with a parameter i to indicate which type of traversal we're performing:

• i = 0: Left boundary traversal
• i = 1: Leaf node collection
• i = 2: Right boundary traversal

This elegant use of DFS with different modes allows us to collect all the boundary nodes in the required order with a single recursive function structure.

Intuition

The key insight is recognizing that the boundary of a binary tree can be broken down into distinct, non-overlapping parts that we can collect separately and then combine.

Think about walking around the perimeter of a tree drawn on paper - you'd naturally trace along the left edge, across the bottom (the leaves), and up the right edge. This visual metaphor directly translates to our algorithm.

The challenge is that these three parts (left boundary, leaves, right boundary) have different traversal rules:

• Left boundary: Always go left when possible, otherwise go right, but stop before reaching a leaf
• Leaves: Visit all nodes and only collect those without children
• Right boundary: Always go right when possible, otherwise go left, but stop before reaching a leaf

Since each part requires a different traversal strategy, we could write three separate DFS functions. However, we can be more elegant by using a single DFS function with a parameter that controls its behavior. This parameter (i in the solution) acts like a "mode switch" that tells the function which traversal rule to follow.

Why does root.left == root.right check for a leaf node? This is a clever way to check if both children are None without explicitly writing root.left is None and root.right is None. When both are None, they're equal.

The reason we reverse the right boundary at the end is because DFS naturally collects nodes from top to bottom, but for the boundary traversal, we need the right boundary from bottom to top (to maintain the counterclockwise order around the tree).

Finally, we handle the root separately at the beginning because it's always part of the boundary but doesn't belong to any of the three categories we're collecting.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a single DFS function with a mode parameter to handle all three types of boundary traversals. Let's walk through each component:

Main Function Structure:

1. First, handle the edge case where the tree has only the root node (when root.left == root.right, meaning both children are None)
2. Initialize the answer list with the root value
3. Create three separate lists for collecting left boundary, leaves, and right boundary
4. Make three DFS calls with different modes
5. Concatenate the results in the correct order

The DFS Function Parameters:

• nums: The list to store collected node values for the current traversal type
• root: The current node being processed
• i: The mode indicator (0 for left boundary, 1 for leaves, 2 for right boundary)

Mode 0 - Left Boundary Traversal: When i == 0, we collect the left boundary:

• Check if the node is not a leaf using root.left != root.right (non-leaf condition)
• If it's not a leaf, add its value to nums
• Prefer going left: if left child exists, recurse on it
• Otherwise, recurse on the right child
• This naturally stops at leaves without including them

Mode 1 - Leaf Collection: When i == 1, we collect all leaves:

• Check if the node is a leaf using root.left == root.right (both children are None)
• If it's a leaf, add its value to nums
• Otherwise, recursively traverse both left and right subtrees
• This performs a complete traversal collecting only leaf nodes in left-to-right order

Mode 2 - Right Boundary Traversal: When i == 2, we collect the right boundary:

• Similar to left boundary but mirror image
• Check if not a leaf, then add to nums
• Prefer going right: if right child exists, recurse on it
• Otherwise, recurse on the left child

Final Assembly:

ans += left + leaves + right[::-1]

The right boundary is reversed using [::-1] because DFS collects nodes top-to-bottom, but we need them bottom-to-top for the boundary traversal order.

Time Complexity: O(n) where n is the number of nodes, as we visit each node at most twice (once for boundary/leaf detection)

Space Complexity: O(n) for storing the result and O(h) for the recursion stack, where h is the height of the tree

Example Walkthrough

Let's walk through a concrete example to understand how the boundary traversal works.

Consider this binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6
       / \
      7   8

Step 1: Add the root

• Start with ans = [1]

Step 2: Collect left boundary (mode 0)

• Start at node 2 (root's left child)
• Node 2 is not a leaf (has children), add it: left = [2]
• Go to node 2's left child (node 4)
• Node 4 is a leaf (no children), stop here
• Result: left = [2]

Step 3: Collect all leaves (mode 1)

• Traverse entire tree looking for leaves
• Starting from node 2:
  • Node 4 is a leaf, add it: leaves = [4]
  • Node 5 has children, skip
  • Node 7 is a leaf, add it: leaves = [4, 7]
  • Node 8 is a leaf, add it: leaves = [4, 7, 8]
• From node 3:
  • Node 6 is a leaf, add it: leaves = [4, 7, 8, 6]
• Result: leaves = [4, 7, 8, 6]

Step 4: Collect right boundary (mode 2)

• Start at node 3 (root's right child)
• Node 3 is not a leaf (has right child), add it: right = [3]
• Go to node 3's right child (node 6)
• Node 6 is a leaf, stop here
• Result: right = [3]

Step 5: Assemble final answer

• Concatenate: ans = [1] + [2] + [4, 7, 8, 6] + [3][::-1]
• Since [3][::-1] = [3], we get:
• Final answer: [1, 2, 4, 7, 8, 6, 3]

Tracing through the DFS calls:

For the left boundary (i=0) starting at node 2:

dfs([2], node=2, i=0)
  - node 2 is not a leaf (has left and right children)
  - Add 2 to nums: [2]
  - Has left child, recurse on node 4
  - dfs([2], node=4, i=0)
    - node 4 is a leaf (no children)
    - Don't add to nums, return

For leaves (i=1) starting at node 2:

dfs([], node=2, i=1)
  - node 2 is not a leaf
  - Recurse on both children
  - dfs([], node=4, i=1)
    - node 4 is a leaf, add 4: [4]
  - dfs([4], node=5, i=1)
    - node 5 is not a leaf
    - Recurse on children...

This example demonstrates how the single DFS function with different modes elegantly handles the three different traversal patterns needed for the complete boundary.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm traverses the binary tree to collect boundary nodes in three parts: left boundary, leaves, and right boundary. Each node in the tree is visited at most once during the traversal:

• The left boundary traversal visits nodes along the leftmost path, which is at most O(h) where h is the height of the tree
• The leaves traversal performs a complete DFS of the entire tree, visiting all n nodes exactly once
• The right boundary traversal visits nodes along the rightmost path, which is at most O(h)

Since the leaves traversal dominates with O(n) operations and each node is processed in constant time, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of:

• The recursion call stack depth, which in the worst case (skewed tree) can be O(n), and in the best case (balanced tree) is O(log n)
• The storage for the result lists: left, leaves, right, and ans, which together can store up to O(n) elements in the worst case when all nodes are part of the boundary
• The final answer list ans which contains the boundary nodes

Therefore, the overall space complexity is O(n) where n is the number of nodes in the binary tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Including the Root in Leaf Collection

One of the most common mistakes is accidentally including the root node when collecting leaves, especially in edge cases where the root is the only node in the tree.

Problem Example:

# Incorrect leaf collection that might include root
def collect_leaves(node):
    if node.left is None and node.right is None:
        leaves.append(node.val)  # Root gets added if it's a leaf!
    # ... rest of traversal
  
# Then calling:
collect_leaves(root)  # Root might be counted twice!

Solution: Start leaf collection from root's children, not from the root itself:

# Correct approach
if root.left:
    collect_boundary(leaf_nodes, root.left, 1)
if root.right:
    collect_boundary(leaf_nodes, root.right, 1)

2. Including Leaves in Left/Right Boundaries

Another frequent error is adding leaf nodes to the left or right boundary collections. The boundary should stop just before reaching a leaf.

Problem Example:

# Incorrect - adds leaves to boundary
def collect_left_boundary(node):
    if node:
        boundary.append(node.val)  # Adds ALL nodes including leaves
        if node.left:
            collect_left_boundary(node.left)
        elif node.right:
            collect_left_boundary(node.right)

Solution: Always check if a node is a leaf before adding it to the boundary:

# Correct - excludes leaves from boundary
is_leaf = (node.left is None and node.right is None)
if not is_leaf:
    boundary_nodes.append(node.val)
    # Continue traversal...

3. Forgetting to Reverse the Right Boundary

The right boundary must be added in reverse order (bottom-up), but DFS naturally collects nodes top-down.

Problem Example:

# Incorrect - adds right boundary in wrong order
result.extend(right_boundary)  # Top-down order, should be bottom-up!

Solution: Reverse the right boundary before adding:

# Correct
result.extend(reversed(right_boundary))
# Or
result.extend(right_boundary[::-1])

4. Incorrect Traversal Priority for Boundaries

Left boundary should prefer left children, right boundary should prefer right children. Mixing these up leads to incorrect boundaries.

Problem Example:

# Incorrect left boundary - wrong child preference
if node.right:  # Should check left first!
    collect_boundary(node.right, 0)
elif node.left:
    collect_boundary(node.left, 0)

Solution: Ensure correct child preference for each boundary type:

# Left boundary - prefer left child
if node.left:
    collect_boundary(boundary_nodes, node.left, 0)
else:
    collect_boundary(boundary_nodes, node.right, 0)

# Right boundary - prefer right child  
if node.right:
    collect_boundary(boundary_nodes, node.right, 2)
else:
    collect_boundary(boundary_nodes, node.left, 2)

5. Not Handling Single-Node Tree Correctly

When the tree has only a root node, it should be returned as-is without being processed as a leaf.

Problem Example:

# Incorrect - might process root twice
result = [root.val]
# ... collect boundaries and leaves including root
# Root appears twice in result!

Solution: Check for single-node tree explicitly:

# Correct
if root.left is None and root.right is None:
    return [root.val]  # Early return for single node
# Continue with normal processing...