LeetCode 545: Boundary of Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to return the boundary of the tree in anti-clockwise order starting from the root.

The boundary consists of three parts:

1. Left boundary
2. Leaf nodes
3. Right boundary in reverse order

There are important rules:

The left boundary is formed by always preferring the left child when moving downward. If no left child exists, move to the right child.

The right boundary similarly prefers the right child first.

The official problem defines the boundary as root, left boundary, leaves, and reversed right boundary, without duplicates. (leetcode.com)

Input and Output

Function shape:

def boundaryOfBinaryTree(root: Optional[TreeNode]) -> list[int]:
    ...

Examples

Consider:

    1
     \
      2
     / \
    3   4

The boundary is:

1 -> 3 -> 4 -> 2

Explanation:

Output:

[1, 3, 4, 2]

Another example:

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

Boundary traversal:

Final order:

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

First Thought: One DFS Around the Tree

A natural idea is to walk around the outside of the tree.

But handling all cases in one traversal becomes complicated:

• Leaves may appear on both sides.
• Left and right boundaries must exclude leaves.
• Right boundary must be reversed.
• Nodes must not repeat.

A cleaner solution is to treat each part independently.

Key Insight

The boundary can be built in exactly this order:

root
+
left boundary
+
all leaves
+
reversed right boundary

Each part has a simple rule.

So instead of trying to solve everything in one DFS, we write three separate traversals:

1. Add left boundary
2. Add leaves
3. Add right boundary

This keeps the logic easy to verify.

Algorithm

1. If the tree is empty, return [].
2. Add the root value.
3. Traverse the left boundary:
   • Prefer left child.
   • Otherwise use right child.
   • Skip leaves.
4. Traverse all leaves:
   • DFS over the whole tree.
   • Add only leaf nodes.
5. Traverse the right boundary:
   • Prefer right child.
   • Otherwise use left child.
   • Skip leaves.
   • Add nodes in reverse order.
6. Return the result.

Correctness

The algorithm adds nodes in exactly the required anti-clockwise boundary order.

The root is added first.

The left boundary traversal starts from the root’s left child and always moves downward along the outer edge of the tree. Leaf nodes are excluded so they are not duplicated later during leaf collection.

The leaf traversal visits every node in the tree and adds exactly those nodes with no children. Since every leaf is visited once and boundary traversals skip leaves, each leaf appears exactly once in the final result.

The right boundary traversal follows the outer right edge of the tree, excluding leaves. Nodes are collected during downward traversal and then appended in reverse order, which produces the required bottom-up right boundary order.

Every boundary node belongs to exactly one of these categories:

• root
• left boundary
• leaf
• right boundary

and the traversal rules prevent duplicates between categories.

Therefore, the algorithm returns the correct tree boundary in anti-clockwise order.

Complexity

Let n be the number of nodes.

h is the tree height.

In a balanced tree:

h = O(log n)

In a skewed tree:

h = O(n)

Implementation

# 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 Optional

class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

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

        boundary = [root.val]

        def add_left_boundary(node: Optional[TreeNode]) -> None:
            while node:
                if not is_leaf(node):
                    boundary.append(node.val)

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

        def add_leaves(node: Optional[TreeNode]) -> None:
            if node is None:
                return

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

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

        def add_right_boundary(node: Optional[TreeNode]) -> None:
            stack = []

            while node:
                if not is_leaf(node):
                    stack.append(node.val)

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

            while stack:
                boundary.append(stack.pop())

        add_left_boundary(root.left)

        if not is_leaf(root):
            add_leaves(root)

        add_right_boundary(root.right)

        return boundary

Code Explanation

We first handle the empty tree:

if root is None:
    return []

The helper:

is_leaf(node)

checks whether a node has no children.

The root is always included first:

boundary = [root.val]

Left Boundary

The left boundary traversal moves downward:

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

This follows the outermost edge.

Leaves are skipped:

if not is_leaf(node):

because leaves are handled separately.

Leaves

The leaf traversal performs DFS over the entire tree.

If a node is a leaf:

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

Otherwise we continue recursively.

Right Boundary

The right boundary traversal is similar to the left boundary, but it prefers the right child first.

The important difference is that right-boundary nodes must appear bottom-up.

So we first collect them into a stack:

stack.append(node.val)

Then reverse the order by popping:

while stack:
    boundary.append(stack.pop())

Edge Cases

Single Node

1

The root is also a leaf.

Output:

[1]

The code avoids duplicate insertion because:

if not is_leaf(root):
    add_leaves(root)

Left-Skewed Tree

    1
   /
  2
 /
3

Boundary:

[1, 2, 3]

Right-Skewed Tree

1
 \
  2
   \
    3

Boundary:

[1, 3, 2]

The right boundary is reversed.

Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(
        1,
        None,
        TreeNode(2, TreeNode(3), TreeNode(4)),
    )
    assert s.boundaryOfBinaryTree(root) == [1, 3, 4, 2]

    root = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(4),
            TreeNode(5, TreeNode(7), TreeNode(8)),
        ),
        TreeNode(
            3,
            None,
            TreeNode(6, TreeNode(9), None),
        ),
    )
    assert s.boundaryOfBinaryTree(root) == [1, 2, 4, 7, 8, 9, 6, 3]

    root = TreeNode(1)
    assert s.boundaryOfBinaryTree(root) == [1]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.boundaryOfBinaryTree(root) == [1, 2, 3]

    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert s.boundaryOfBinaryTree(root) == [1, 3, 2]

    print("all tests passed")

run_tests()