Boundary Traversal of Binary Tree

Boundary traversal collects the “outline” of a binary tree in anticlockwise order. Think of tracing a finger around the tree’s perimeter: start at the root, go down the left edge, across the bottom (leaves), and back up the right edge. This problem is a favorite in interviews at companies like Amazon and Microsoft.

Problem statement

Given the root of a binary tree, return the boundary traversal in anticlockwise order. The boundary consists of three parts:

1. Left boundary: Nodes on the path from root to the leftmost leaf (excluding the leaf itself)
2. Leaf nodes: All leaves from left to right
3. Right boundary: Nodes on the path from the rightmost leaf back to root (excluding the leaf, in reverse order)

The root is always part of the boundary (counted once).

TreeNode definition

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

Example walkthrough

           1
          / \
         2   3
        / \   \
       4   5   7
      /   / \   \
     8   9  10  11

Left boundary (root down-left, excluding leaves): [1, 2, 4]

• Start at root (1), go to left child (2), then left child (4)
• Stop at 4 because its child (8) is a leaf

Leaf nodes (left to right): [8, 9, 10, 11]

Right boundary (root down-right, reversed, excluding leaves): [7, 3]

• Start at root, go right (3), then right (7)
• Reverse to get [7, 3]

Result: [1, 2, 4, 8, 9, 10, 11, 7, 3]

Note: the root (1) is part of the left boundary and is not repeated.

Approach 1: three separate passes

The cleanest approach separates the problem into three independent functions:

def boundaryOfBinaryTree(root):
    """
    Boundary traversal: left boundary + leaves + right boundary (reversed).
    Time: O(n)  Space: O(n)
    """
    if not root:
        return []

    # Single node is its own boundary
    if not root.left and not root.right:
        return [root.val]

    result = [root.val]

    # 1. Left boundary (top to bottom, excluding leaves)
    addLeftBoundary(root.left, result)

    # 2. All leaves (left to right)
    addLeaves(root, result)

    # 3. Right boundary (bottom to top, excluding leaves)
    right_boundary = []
    addRightBoundary(root.right, right_boundary)
    result.extend(reversed(right_boundary))

    return result


def addLeftBoundary(node, result):
    """
    Collect left boundary nodes (excluding leaves).
    Always prefer left child; if no left, take right.
    """
    while node:
        # Skip leaves
        if node.left or node.right:
            result.append(node.val)

        # Prefer left, fallback to right
        if node.left:
            node = node.left
        else:
            node = node.right


def addLeaves(node, result):
    """Collect all leaf nodes using DFS (left to right)."""
    if not node:
        return

    if not node.left and not node.right:
        result.append(node.val)
        return

    addLeaves(node.left, result)
    addLeaves(node.right, result)


def addRightBoundary(node, result):
    """
    Collect right boundary nodes (excluding leaves).
    Always prefer right child; if no right, take left.
    """
    while node:
        if node.left or node.right:
            result.append(node.val)

        if node.right:
            node = node.right
        else:
            node = node.left

Why separate the three parts?

Each part has different traversal logic:

• Left boundary: iterative, prefer-left descent
• Leaves: recursive DFS, in-order leaf collection
• Right boundary: iterative, prefer-right descent, then reverse

Separating them makes each function simple and testable.

Left boundary logic explained

The left boundary walks down from root.left, always preferring the left child. If there is no left child, it takes the right child instead (because the boundary “wraps” to the nearest available path). It stops before leaves because leaves are collected separately.

         1
        / \
       2   3
        \
         5
        / \
       9  10

Left boundary: [2, 5]
- Start at 2 (root.left)
- 2 has no left child, take right → 5
- 5 has children (not a leaf), add 5
- 5's left child 9 is a leaf, stop

Right boundary logic explained

Same idea but mirrored — prefer the right child, fallback to left. Collect in top-to-bottom order, then reverse at the end.

Approach 2: single DFS with flags

An alternative uses a single DFS traversal with flags to mark whether a node is on the left boundary, right boundary, or a leaf:

def boundaryOfBinaryTree_single(root):
    """
    Single-pass DFS with boundary classification.
    Time: O(n)  Space: O(h) + O(n) for result
    """
    if not root:
        return []

    result = [root.val]
    right_boundary = []

    def dfs(node, is_left_boundary, is_right_boundary):
        if not node:
            return

        is_leaf = not node.left and not node.right

        if is_leaf:
            result.append(node.val)
        elif is_left_boundary:
            result.append(node.val)
        elif is_right_boundary:
            right_boundary.append(node.val)

        # Left child inherits left boundary status
        # Right child inherits right boundary status
        # If on left boundary and no left child, right child becomes left boundary
        left_is_lb = is_left_boundary
        left_is_rb = is_right_boundary and not node.right

        right_is_rb = is_right_boundary
        right_is_lb = is_left_boundary and not node.left

        dfs(node.left, left_is_lb, left_is_rb)
        dfs(node.right, right_is_lb, right_is_rb)

    dfs(root.left, True, False)
    dfs(root.right, False, True)

    result.extend(reversed(right_boundary))
    return result

This approach is more complex but does everything in a single traversal.

Approach 3: iterative with explicit stacks

For those who prefer fully iterative solutions:

from collections import deque

def boundaryOfBinaryTree_iterative(root):
    """Fully iterative boundary traversal."""
    if not root:
        return []
    if not root.left and not root.right:
        return [root.val]

    result = [root.val]

    # Left boundary (iterative)
    node = root.left
    while node:
        if node.left or node.right:
            result.append(node.val)
        node = node.left if node.left else node.right

    # Leaves (iterative using stack)
    stack = [root]
    while stack:
        node = stack.pop()
        if not node.left and not node.right:
            result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    # Right boundary (iterative, collect then reverse)
    right_boundary = []
    node = root.right
    while node:
        if node.left or node.right:
            right_boundary.append(node.val)
        node = node.right if node.right else node.left

    result.extend(reversed(right_boundary))
    return result

Edge cases

Single node

root = TreeNode(1)
# Output: [1]
# The root is a leaf and the entire boundary

Left-skewed tree

     1
    /
   2
  /
 3

Left boundary: [1, 2] (3 is a leaf) Leaves: [3] Right boundary: empty (no right subtree from root) Result: [1, 2, 3]

Right-skewed tree

1
 \
  2
   \
    3

Left boundary: empty (no left subtree from root) Leaves: [3] Right boundary: [2] (reversed from [2]) Result: [1, 3, 2]

Root with only left subtree

      1
     /
    2
   / \
  4   5

Left boundary: [2] (4 is a leaf) Leaves: [4, 5] Right boundary: empty Result: [1, 2, 4, 5]

Test cases

def test_boundary():
    # Single node
    assert boundaryOfBinaryTree(TreeNode(1)) == [1]

    # Two nodes (left child)
    root = TreeNode(1, TreeNode(2))
    assert boundaryOfBinaryTree(root) == [1, 2]

    # Two nodes (right child)
    root = TreeNode(1, None, TreeNode(3))
    assert boundaryOfBinaryTree(root) == [1, 3]

    # Complete tree
    root = TreeNode(1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7))
    )
    # Left boundary: [2], Leaves: [4,5,6,7], Right boundary: [3]
    assert boundaryOfBinaryTree(root) == [1, 2, 4, 5, 6, 7, 3]

Common mistakes

1. Including leaves in left/right boundary: Leaves are collected separately. The left and right boundary functions must skip leaf nodes.

2. Double-counting the root: The root is added once at the start. The left boundary starts from root.left and right boundary from root.right.

3. Forgetting to reverse the right boundary: The right boundary is collected top-to-bottom but should appear bottom-to-top in the final result.

4. Not handling single-child nodes: When a left boundary node has no left child, its right child becomes part of the left boundary. Same for the right boundary with no right child.

5. Empty tree or single node: Return [] for null root and [root.val] for a single node.

Complexity analysis

Time: O(n)

• Left boundary: O(h) where h is the height
• Leaf collection: O(n) — visits every node once
• Right boundary: O(h)
• Total: O(n) since leaf collection dominates

Space: O(n)

• Result array: O(n) in the worst case (all nodes on boundary)
• Recursion stack for leaf collection: O(h)
• Right boundary temporary list: O(h)

Variation: clockwise boundary

Some problems ask for clockwise boundary instead of anticlockwise. Simply swap the order:

def clockwiseBoundary(root):
    """Clockwise: root + right boundary + reversed leaves + left boundary reversed."""
    if not root:
        return []
    if not root.left and not root.right:
        return [root.val]

    result = [root.val]

    # Right boundary (top to bottom)
    addRightBoundary(root.right, result)

    # Leaves (right to left — reverse of normal)
    leaves = []
    addLeaves(root, leaves)
    result.extend(reversed(leaves))

    # Left boundary (bottom to top)
    left_boundary = []
    addLeftBoundary(root.left, left_boundary)
    result.extend(reversed(left_boundary))

    return result

Practice problems

Problem	Difficulty	Link
Boundary of Binary Tree	Medium	LeetCode 545
Binary Tree Right Side View	Medium	LeetCode 199
Leaf-Similar Trees	Easy	LeetCode 872
Sum of Left Leaves	Easy	LeetCode 404
Find Leaves of Binary Tree	Medium	LeetCode 366

Key takeaways

1. Boundary traversal has three distinct parts: left boundary, leaves, right boundary (reversed)
2. Left boundary prefers the left child; right boundary prefers the right child
3. Both boundaries exclude leaf nodes to avoid duplication
4. The root is added separately and is never duplicated
5. Separating into three functions is the clearest and most maintainable approach