LeetCode 545 - Boundary of Binary Tree

This problem asks us to compute the boundary traversal of a binary tree in a very specific order. The boundary is formed by combining four parts: 1. The root node 2. The left boundary, excluding leaves 3. All leaf nodes from left to right 4.

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 545

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to compute the boundary traversal of a binary tree in a very specific order. The boundary is formed by combining four parts:

  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

The challenge is not simply traversing the tree, but carefully avoiding duplicates while preserving the required ordering.

The input is the root of a binary tree. Each node contains an integer value and references to left and right child nodes. The output should be a list of integers representing the tree boundary in clockwise order starting from the root.

The constraints allow up to 10^4 nodes, which means an efficient linear traversal is expected. Any solution that repeatedly scans large portions of the tree could become inefficient. Since the tree may also be highly unbalanced, recursive depth can approach O(n) in the worst case.

Several details in the definition are important:

  • A leaf node is any node with no children.
  • The root itself is not considered a leaf for the leaf collection phase.
  • The left boundary excludes the leftmost leaf.
  • The right boundary excludes the rightmost leaf.
  • Leaf nodes should appear exactly once in the final answer.

These rules create several tricky edge cases.

For example:

  • A tree with only one node should return just that node.
  • A tree with only left children should not duplicate leaves.
  • A tree with only right children should still correctly reverse the right boundary.
  • A skewed tree may cause the left or right boundary logic to fall back to alternate child directions.
  • A node can belong to both a boundary path and the leaf set, so duplicate prevention matters.

The core difficulty is carefully separating the three traversal responsibilities:

  • collecting the left boundary,
  • collecting leaves,
  • collecting the right boundary in reverse order.

Approaches

Brute Force Approach

A brute force strategy would be to explicitly simulate the boundary definition using multiple complete traversals and extra bookkeeping structures.

One possible brute force method is:

  • Traverse the tree to identify every root-to-leaf path.
  • Determine the leftmost and rightmost paths.
  • Use sets or maps to track which nodes belong to which category.
  • Merge the results carefully while removing duplicates.

This approach works because the boundary definition is based on structural positions in the tree. By computing all relevant paths and node classifications, we can reconstruct the correct ordering.

However, this method is unnecessarily complicated and inefficient. It may require:

  • storing many paths,
  • revisiting nodes multiple times,
  • using additional memory for duplicate handling.

For large trees, this becomes wasteful.

Optimal Approach

The key observation is that the boundary naturally divides into three independent traversals:

  1. Left boundary traversal
  2. Leaf traversal
  3. Right boundary traversal

Each traversal can be performed in linear time while avoiding duplicates.

The optimal solution works as follows:

  • Add the root first.
  • Walk down the left boundary, always preferring the left child over the right child, and stop before leaves.
  • Perform a DFS to collect all leaves from left to right.
  • Walk down the right boundary, always preferring the right child over the left child, store the nodes temporarily, then reverse them before appending.

This works because every boundary node belongs to exactly one of these structural categories:

  • left edge,
  • leaf,
  • right edge,
  • or root.

By excluding leaves from both boundary traversals, we ensure each node appears only once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Multiple traversals and path storage
Optimal O(n) O(h) Single-pass style traversal with DFS

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

  1. Start by handling the empty tree case.

If the root is None, return an empty list immediately. 2. Create a helper function to determine whether a node is a leaf.

A node is a leaf if both left and right are None.

This helper simplifies duplicate prevention throughout the algorithm. 3. Initialize the result list with the root value.

The root is always part of the boundary.

However, if the tree contains only the root node, we should return immediately because the root should not also be treated as a leaf later. 4. Traverse the left boundary.

Begin from root.left.

At each step:

  • If the current node is not a leaf, add it to the result.
  • Prefer moving to the left child.
  • If no left child exists, move to the right child.

This follows the exact left boundary definition from the problem statement. 5. Collect all leaf nodes using DFS.

Perform a depth-first traversal over the entire tree.

For every node:

  • If it is a leaf, add it to the result.
  • Otherwise recursively explore the left subtree first, then the right subtree.

Left-first DFS guarantees leaves are collected from left to right. 6. Traverse the right boundary.

Begin from root.right.

At each step:

  • If the node is not a leaf, store it in a temporary list.
  • Prefer moving to the right child.
  • If no right child exists, move to the left child.

After traversal completes, reverse the temporary list and append it to the result.

Reversal is necessary because the boundary definition requires bottom-up ordering on the right side. 7. Return the final result list.

Why it works

The algorithm works because every boundary node belongs to exactly one logical section:

  • The root is added once at the beginning.
  • Left boundary nodes are collected top-down without leaves.
  • Leaves are collected separately in left-to-right order.
  • Right boundary nodes are collected bottom-up without leaves.

Since leaves are excluded from both boundary traversals, no node is duplicated. Since DFS visits leaves left-first, the required ordering is preserved.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import List, Optional

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

        def is_leaf(node: TreeNode) -> bool:
            return not node.left and not node.right

        # Single node tree
        if is_leaf(root):
            return [root.val]

        boundary = [root.val]

        # Add left boundary
        current = root.left

        while current:
            if not is_leaf(current):
                boundary.append(current.val)

            if current.left:
                current = current.left
            else:
                current = current.right

        # Add leaves
        def add_leaves(node: Optional[TreeNode]) -> None:
            if not node:
                return

            if is_leaf(node):
                boundary.append(node.val)
                return

            add_leaves(node.left)
            add_leaves(node.right)

        add_leaves(root)

        # Add right boundary
        current = root.right
        right_boundary = []

        while current:
            if not is_leaf(current):
                right_boundary.append(current.val)

            if current.right:
                current = current.right
            else:
                current = current.left

        boundary.extend(reversed(right_boundary))

        return boundary

The implementation begins with edge case handling for an empty tree and a single-node tree. This prevents duplicate inclusion of the root during leaf traversal.

The is_leaf helper centralizes leaf detection logic. Since the problem specifically excludes leaves from left and right boundary traversals, this helper is used repeatedly throughout the solution.

The left boundary traversal iteratively walks downward while always prioritizing the left child. If a left child does not exist, the traversal falls back to the right child. This exactly matches the problem definition.

The leaf collection phase uses DFS. A recursive traversal naturally visits leaves in left-to-right order because the left subtree is processed before the right subtree.

The right boundary traversal mirrors the left boundary traversal. However, nodes are stored in a temporary list because the final boundary requires reverse ordering on the right side.

Finally, the reversed right boundary is appended to the result.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func boundaryOfBinaryTree(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    isLeaf := func(node *TreeNode) bool {
        return node.Left == nil && node.Right == nil
    }

    if isLeaf(root) {
        return []int{root.Val}
    }

    boundary := []int{root.Val}

    // Add left boundary
    current := root.Left

    for current != nil {
        if !isLeaf(current) {
            boundary = append(boundary, current.Val)
        }

        if current.Left != nil {
            current = current.Left
        } else {
            current = current.Right
        }
    }

    // Add leaves
    var addLeaves func(node *TreeNode)

    addLeaves = func(node *TreeNode) {
        if node == nil {
            return
        }

        if isLeaf(node) {
            boundary = append(boundary, node.Val)
            return
        }

        addLeaves(node.Left)
        addLeaves(node.Right)
    }

    addLeaves(root)

    // Add right boundary
    current = root.Right
    rightBoundary := []int{}

    for current != nil {
        if !isLeaf(current) {
            rightBoundary = append(rightBoundary, current.Val)
        }

        if current.Right != nil {
            current = current.Right
        } else {
            current = current.Left
        }
    }

    // Reverse append
    for i := len(rightBoundary) - 1; i >= 0; i-- {
        boundary = append(boundary, rightBoundary[i])
    }

    return boundary
}

The Go implementation follows the same structure as the Python solution. The primary differences come from language mechanics.

Go uses explicit nil checks instead of Python truthiness. Slices are used for dynamic arrays, and reversing is handled manually using a reverse loop instead of Python's reversed() helper.

Recursive DFS is implemented using a function variable declaration because Go requires recursive anonymous functions to be declared before assignment.

Worked Examples

Example 1

Tree:

    1
     \
      2
     / \
    3   4

Input:

root = [1,null,2,3,4]

Step 1: Add Root

Action Boundary
Add root 1 [1]

Step 2: Left Boundary

root.left is None, so no nodes are added.

Action Boundary
No left boundary [1]

Step 3: Collect Leaves

DFS traversal order:

  • Visit 3, leaf
  • Visit 4, leaf
Leaf Found Boundary
3 [1, 3]
4 [1, 3, 4]

Step 4: Right Boundary

Traversal path:

  • 2
  • 4

Node 4 is a leaf, so it is skipped.

Temporary right boundary:

[2]

Reverse and append:

Action Boundary
Append reversed right boundary [1, 3, 4, 2]

Final answer:

[1,3,4,2]

Example 2

Tree:

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

Input:

root = [1,2,3,4,5,6,null,null,null,7,8,9,10]

Step 1: Add Root

Action Boundary
Add root 1 [1]

Step 2: Left Boundary

Traversal:

  • 2
  • 4

Node 4 is a leaf, so skip it.

Added Boundary
2 [1, 2]

Step 3: Collect Leaves

DFS left-to-right order:

  • 4
  • 7
  • 8
  • 9
  • 10
Leaf Found Boundary
4 [1, 2, 4]
7 [1, 2, 4, 7]
8 [1, 2, 4, 7, 8]
9 [1, 2, 4, 7, 8, 9]
10 [1, 2, 4, 7, 8, 9, 10]

Step 4: Right Boundary

Traversal:

  • 3
  • 6
  • 10

Node 10 is a leaf, so skip it.

Temporary list:

[3, 6]

Reverse:

[6, 3]

Append:

Action Boundary
Append reversed right boundary [1,2,4,7,8,9,10,6,3]

Final answer:

[1,2,4,7,8,9,10,6,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited at most a constant number of times
Space O(h) Recursive DFS stack depth equals tree height

The left boundary traversal touches only boundary nodes. The right boundary traversal also touches only boundary nodes. The DFS leaf collection visits every node exactly once.

Therefore, total runtime is linear in the number of nodes.

The only extra space beyond the output list comes from recursion depth and the temporary right boundary list. In the worst case of a skewed tree, recursion depth becomes O(n).

Test Cases

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

solution = Solution()

# Example 1
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.left = TreeNode(3)
root1.right.right = TreeNode(4)

assert solution.boundaryOfBinaryTree(root1) == [1, 3, 4, 2]  # right-heavy tree

# Example 2
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
root2.left.left = TreeNode(4)
root2.left.right = TreeNode(5)
root2.left.right.left = TreeNode(7)
root2.left.right.right = TreeNode(8)
root2.right.left = TreeNode(6)
root2.right.left.left = TreeNode(9)
root2.right.left.right = TreeNode(10)

assert solution.boundaryOfBinaryTree(root2) == [1, 2, 4, 7, 8, 9, 10, 6, 3]  # balanced tree

# Single node
root3 = TreeNode(1)

assert solution.boundaryOfBinaryTree(root3) == [1]  # root only

# Left skewed tree
root4 = TreeNode(1)
root4.left = TreeNode(2)
root4.left.left = TreeNode(3)
root4.left.left.left = TreeNode(4)

assert solution.boundaryOfBinaryTree(root4) == [1, 2, 3, 4]  # left boundary only

# Right skewed tree
root5 = TreeNode(1)
root5.right = TreeNode(2)
root5.right.right = TreeNode(3)
root5.right.right.right = TreeNode(4)

assert solution.boundaryOfBinaryTree(root5) == [1, 4, 3, 2]  # reversed right boundary

# Tree where boundary must fall back to alternate child
root6 = TreeNode(1)
root6.left = TreeNode(2)
root6.left.right = TreeNode(3)

assert solution.boundaryOfBinaryTree(root6) == [1, 2, 3]  # fallback from left to right child

# Full binary tree
root7 = TreeNode(1)
root7.left = TreeNode(2)
root7.right = TreeNode(3)
root7.left.left = TreeNode(4)
root7.left.right = TreeNode(5)
root7.right.left = TreeNode(6)
root7.right.right = TreeNode(7)

assert solution.boundaryOfBinaryTree(root7) == [1, 2, 4, 5, 6, 7, 3]  # standard full tree

# Empty tree
assert solution.boundaryOfBinaryTree(None) == []  # no nodes
Test Why
Example 1 Validates right boundary handling
Example 2 Validates complete mixed traversal
Single node Ensures root is not duplicated as leaf
Left skewed tree Tests pure left boundary traversal
Right skewed tree Tests reverse right boundary logic
Alternate child fallback Tests boundary fallback rules
Full binary tree Validates standard balanced behavior
Empty tree Ensures null input handling

Edge Cases

Single Node Tree

A tree containing only the root is one of the most important edge cases. A naive implementation might add the root once as the root and again during leaf traversal, producing duplicates.

The implementation avoids this by explicitly checking whether the root is a leaf before starting the normal algorithm. If so, it immediately returns [root.val].

Skewed Trees

A completely left-skewed or right-skewed tree can expose flaws in boundary traversal logic. In these cases, nearly every node belongs to the boundary.

For example, in a right-skewed tree, the right boundary must appear in reverse order, while the leaf should appear only once.

The implementation correctly excludes leaves during boundary traversal and separately appends them during DFS, preventing duplication.

Missing Preferred Child

The problem definition states that if a left boundary node does not have a left child, the traversal should continue through the right child. The same rule applies symmetrically on the right side.

This can easily be overlooked.

For example:

    1
   /
  2
   \
    3

Node 3 is still structurally part of the left side of the tree.

The implementation handles this by:

  • preferring left first during left traversal,
  • otherwise falling back to right.

The right boundary traversal mirrors this behavior in reverse.