Boundary of Binary Tree

MEDIUMProblemSolve External Links

Description

Given the root of a binary tree, return its boundary traversal in anti-clockwise order, starting from the root.

The boundary of a binary tree consists of three parts combined in this order:

Left Boundary: Starting from the root's left child, walk downward along the leftmost path. At each node, prefer the left child; if there is no left child, take the right child. Exclude leaf nodes from this list.
Leaf Nodes: All leaf nodes of the tree, collected from left to right.
Right Boundary: Starting from the root's right child, walk downward along the rightmost path. At each node, prefer the right child; if there is no right child, take the left child. Exclude leaf nodes, and add these nodes in bottom-to-top (reverse) order.

The root node is always included as the first element of the boundary. Each node appears at most once in the result.

Binary tree with boundary nodes highlighted showing the anti-clockwise traversal path

Examples

Example 1

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

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

Explanation: The tree looks like:

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

Root: [1]
Left boundary (top-down, excluding leaves): [2] — walk from node 2: its left child 4 is a leaf, so stop
Leaves (left to right): [4, 8, 9, 6, 7]
Right boundary (bottom-up, excluding leaves): [3] — walk from node 3: its right child 7 is a leaf, so stop
Combined: [1] + [2] + [4, 8, 9, 6, 7] + [3] = [1, 2, 4, 8, 9, 6, 7, 3]

Example 2

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

Output: [1, 3, 4, 2]

Explanation: The tree looks like:

Root: [1]
Left boundary: root has no left child → empty
Leaves (left to right): [3, 4]
Right boundary (bottom-up, excluding leaves): [2] — node 2 is not a leaf
Combined: [1] + [] + [3, 4] + [2] = [1, 3, 4, 2]

Example 3

Input: root = [1]

Output: [1]

Explanation: A single node is both the root and a leaf. The boundary contains just this one node.

Constraints

1 ≤ number of nodes ≤ 10^4
-1000 ≤ Node.val ≤ 1000

Editorial

Brute Force

Intuition

The boundary of a binary tree traces an anti-clockwise path around the tree's perimeter. Think of it like walking around the outside of a building: you start at the front door (root), walk down the left wall (left boundary), along the ground floor (leaves from left to right), and then back up the right wall (right boundary from bottom to top).

The most direct approach decomposes the boundary into three independent sub-problems:

Left boundary: Walk down the leftmost path from root.left, always preferring the left child, collecting non-leaf nodes.
Leaves: Perform a full DFS of the entire tree, collecting every node that has no children.
Right boundary: Walk down the rightmost path from root.right, always preferring the right child, collecting non-leaf nodes, then reverse the collected list.

In this brute force version, each sub-problem is solved by a separate recursive function. The results are stored in three intermediate lists and combined at the end.

Step-by-Step Explanation

Let's trace through with the tree:

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

Step 1: Add root (1) to result. result = [1].

Step 2: Left boundary pass — start at root.left = node 2. Node 2 has children (4 and 5) → it is not a leaf → add 2 to left_bound. left_bound = [2].

Step 3: Continue left boundary walk. Node 2 has a left child (4). Move to 4. Node 4 has no children → it IS a leaf → stop. Left boundary = [2]. We walked through the entire left subtree structure just to find these boundary nodes.

Step 4: Leaf collection pass — full DFS of all 9 nodes. Visit nodes in preorder: 1 (not leaf), 2 (not leaf), 4 (LEAF → add), 5 (not leaf), 8 (LEAF → add), 9 (LEAF → add), 3 (not leaf), 6 (LEAF → add), 7 (LEAF → add). leaves = [4, 8, 9, 6, 7].

Step 5: Right boundary pass — start at root.right = node 3. Node 3 has children (6 and 7) → not a leaf → add 3 to right_bound. right_bound = [3].

Step 6: Continue right boundary walk. Node 3 has a right child (7). Move to 7. Node 7 has no children → leaf → stop. right_bound = [3]. Reverse → [3].

Step 7: Combine all parts: result = [1] + [2] + [4, 8, 9, 6, 7] + [3] = [1, 2, 4, 8, 9, 6, 7, 3].

Recursive Three-Pass Boundary Collection — Watch how three separate recursive passes collect the left boundary, all leaves, and the right boundary, then combine them into the final result.

Algorithm

Add root value to result. If root is a leaf, return [root.val]
Collect left boundary (recursive): Start at root.left. While the node is not null and not a leaf, add its value, then move to its left child (or right child if no left exists)
Collect leaves (recursive DFS): Traverse the entire tree. At each node, if it has no children, add its value
Collect right boundary (recursive): Start at root.right. While the node is not null and not a leaf, add its value, then move to its right child (or left child if no right exists). Reverse the collected list
Return result + left_boundary + leaves + reversed(right_boundary)

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        result.push_back(root->val);
        if (isLeaf(root)) return result;
        
        vector<int> leftBound, leaves, rightBound;
        collectLeft(root->left, leftBound);
        collectLeaves(root, leaves);
        collectRight(root->right, rightBound);
        reverse(rightBound.begin(), rightBound.end());
        
        for (int v : leftBound) result.push_back(v);
        for (int v : leaves) result.push_back(v);
        for (int v : rightBound) result.push_back(v);
        return result;
    }

private:
    bool isLeaf(TreeNode* node) {
        return !node->left && !node->right;
    }
    
    void collectLeft(TreeNode* node, vector<int>& res) {
        if (!node || isLeaf(node)) return;
        res.push_back(node->val);
        if (node->left) collectLeft(node->left, res);
        else collectLeft(node->right, res);
    }
    
    void collectLeaves(TreeNode* node, vector<int>& res) {
        if (!node) return;
        if (isLeaf(node)) { res.push_back(node->val); return; }
        collectLeaves(node->left, res);
        collectLeaves(node->right, res);
    }
    
    void collectRight(TreeNode* node, vector<int>& res) {
        if (!node || isLeaf(node)) return;
        res.push_back(node->val);
        if (node->right) collectRight(node->right, res);
        else collectRight(node->left, res);
    }
};

from typing import Optional, List

class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = [root.val]
        if not root.left and not root.right:
            return result
        
        left_bound = []
        self._collect_left(root.left, left_bound)
        
        leaves = []
        self._collect_leaves(root, leaves)
        
        right_bound = []
        self._collect_right(root.right, right_bound)
        
        return result + left_bound + leaves + right_bound[::-1]
    
    def _is_leaf(self, node):
        return not node.left and not node.right
    
    def _collect_left(self, node, res):
        if not node or self._is_leaf(node):
            return
        res.append(node.val)
        if node.left:
            self._collect_left(node.left, res)
        else:
            self._collect_left(node.right, res)
    
    def _collect_leaves(self, node, res):
        if not node:
            return
        if self._is_leaf(node):
            res.append(node.val)
            return
        self._collect_leaves(node.left, res)
        self._collect_leaves(node.right, res)
    
    def _collect_right(self, node, res):
        if not node or self._is_leaf(node):
            return
        res.append(node.val)
        if node.right:
            self._collect_right(node.right, res)
        else:
            self._collect_right(node.left, res)

import java.util.*;

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        result.add(root.val);
        if (isLeaf(root)) return result;
        
        List<Integer> leftBound = new ArrayList<>();
        collectLeft(root.left, leftBound);
        
        List<Integer> leaves = new ArrayList<>();
        collectLeaves(root, leaves);
        
        List<Integer> rightBound = new ArrayList<>();
        collectRight(root.right, rightBound);
        Collections.reverse(rightBound);
        
        result.addAll(leftBound);
        result.addAll(leaves);
        result.addAll(rightBound);
        return result;
    }
    
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
    
    private void collectLeft(TreeNode node, List<Integer> res) {
        if (node == null || isLeaf(node)) return;
        res.add(node.val);
        if (node.left != null) collectLeft(node.left, res);
        else collectLeft(node.right, res);
    }
    
    private void collectLeaves(TreeNode node, List<Integer> res) {
        if (node == null) return;
        if (isLeaf(node)) { res.add(node.val); return; }
        collectLeaves(node.left, res);
        collectLeaves(node.right, res);
    }
    
    private void collectRight(TreeNode node, List<Integer> res) {
        if (node == null || isLeaf(node)) return;
        res.add(node.val);
        if (node.right != null) collectRight(node.right, res);
        else collectRight(node.left, res);
    }
}

Complexity Analysis

Time Complexity: O(n)

The left boundary walk visits at most h nodes (one per level). The leaf DFS visits all n nodes. The right boundary walk visits at most h nodes. Total: O(h + n + h) = O(n), since h ≤ n.

Space Complexity: O(n)

Three intermediate lists are created: left_bound (up to h elements), leaves (up to n/2 elements in a complete tree), and right_bound (up to h elements). The recursion stack for the leaf DFS uses O(h) space. The right_bound list reversal requires O(h) additional work. Total auxiliary space: O(n) due to the intermediate lists and their combination.

Why This Approach Is Not Efficient

While the recursive approach correctly computes the boundary in O(n) time, it has two inefficiencies:

Unnecessary intermediate storage: Three separate lists (left_bound, leaves, right_bound) are allocated, filled, and then merged into the final result. This means every boundary node is stored twice — once in its part-specific list and once in the combined result. For a tree with 10,000 nodes, this doubles the memory usage.
Recursive overhead for linear paths: The left and right boundary paths are simple linear chains (always go left, or always go right). Using recursion for these adds function call overhead — stack frame allocation, argument passing, return value propagation — for what is essentially a while loop. Each recursive call for the boundary walk does nothing more than: check leaf → add value → move one step.
Right boundary reversal: Collecting the right boundary top-down and then reversing it requires an extra O(h) pass. We can avoid this by appending directly in the correct order.

The optimal approach replaces recursion with iterative while loops for the boundary walks, appends directly to a single result list (no intermediate lists), and handles the right boundary reversal inline.

Optimal Approach - Iterative Boundary Walks with DFS Leaves

Intuition

The key insight is that the left and right boundary paths are linear chains — at each step, you move to exactly one child (left preferred for left boundary, right preferred for right boundary). There is no branching, no backtracking. A recursive function for a non-branching path is overkill; a simple while loop is cleaner and avoids stack overhead.

Think of it this way:

Left boundary: Walk down a staircase, always stepping left. If there is no left step, take a right step. Stop when you reach the ground floor (a leaf). This is a while loop.
Leaves: You DO need to search the entire building (tree) to find all ground-floor rooms (leaves). DFS is appropriate here because the leaves are scattered throughout the tree.
Right boundary: Walk down the right staircase, same idea. But since we need bottom-to-top order, collect into a small temporary list and reverse it (or use a stack).

The optimized approach:

Add root value
Walk left boundary with a while loop — append directly to result
DFS for leaves — append directly to result
Walk right boundary with a while loop — collect in temp, reverse, append

Step-by-Step Explanation

Let's trace through with the same tree:

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

Step 1: Add root (1). result = [1].

Step 2: Iterative left boundary walk. Set curr = root.left = node 2.

Step 3: curr = 2. Not a leaf (has children 4, 5) → append 2. Move: curr = 2.left = 4.

Step 4: curr = 4. IS a leaf (no children) → stop. Left boundary walk done. result = [1, 2]. Only 2 nodes visited!

Step 5: DFS for leaves from root. Visit n4: leaf → append 4. result = [1, 2, 4].

Step 6: DFS: n5 is not a leaf. Visit n8: leaf → append 8. result = [1, 2, 4, 8].

Step 7: Visit n9: leaf → append 9. result = [1, 2, 4, 8, 9].

Step 8: Enter right subtree. Visit n6: leaf → append 6. result = [1, 2, 4, 8, 9, 6].

Step 9: Visit n7: leaf → append 7. result = [1, 2, 4, 8, 9, 6, 7].

Step 10: Iterative right boundary walk. Set curr = root.right = node 3. curr = 3, not a leaf → add to temp = [3]. Move: curr = 3.right = 7. curr = 7 is a leaf → stop.

Step 11: Reverse temp = [3] → [3]. Append to result. Final result = [1, 2, 4, 8, 9, 6, 7, 3].

Iterative Boundary Walks + DFS Leaf Collection — Watch how the left and right boundary paths are walked iteratively with simple while loops, while only the leaf collection requires a full DFS.

Algorithm

If root is null, return []. Add root.val to result. If root is a leaf, return result
Left boundary (iterative while loop):
- Set curr = root.left
- While curr is not null: if curr is not a leaf, append curr.val to result. Move: curr = curr.left if it exists, else curr = curr.right
Leaf nodes (DFS):
- Recursively traverse the entire tree. At each node, if it is a leaf (no children), append its value to result
Right boundary (iterative while loop):
- Set curr = root.right
- While curr is not null: if curr is not a leaf, append curr.val to a temporary list. Move: curr = curr.right if it exists, else curr = curr.left
- Reverse the temporary list and append to result
Return result

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        result.push_back(root->val);
        if (isLeaf(root)) return result;
        
        // Iterative left boundary walk
        TreeNode* curr = root->left;
        while (curr) {
            if (!isLeaf(curr)) result.push_back(curr->val);
            curr = curr->left ? curr->left : curr->right;
        }
        
        // DFS for leaf nodes
        addLeaves(root, result);
        
        // Iterative right boundary walk (reversed)
        vector<int> temp;
        curr = root->right;
        while (curr) {
            if (!isLeaf(curr)) temp.push_back(curr->val);
            curr = curr->right ? curr->right : curr->left;
        }
        for (int i = temp.size() - 1; i >= 0; i--) {
            result.push_back(temp[i]);
        }
        
        return result;
    }

private:
    bool isLeaf(TreeNode* node) {
        return !node->left && !node->right;
    }
    
    void addLeaves(TreeNode* node, vector<int>& result) {
        if (!node) return;
        if (isLeaf(node)) {
            result.push_back(node->val);
            return;
        }
        addLeaves(node->left, result);
        addLeaves(node->right, result);
    }
};

from typing import Optional, List

class Solution:
    def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        def is_leaf(node):
            return not node.left and not node.right
        
        result = [root.val]
        if is_leaf(root):
            return result
        
        # Iterative left boundary walk
        curr = root.left
        while curr:
            if not is_leaf(curr):
                result.append(curr.val)
            curr = curr.left if curr.left else curr.right
        
        # DFS for leaf nodes
        def add_leaves(node):
            if not node:
                return
            if is_leaf(node):
                result.append(node.val)
                return
            add_leaves(node.left)
            add_leaves(node.right)
        
        add_leaves(root)
        
        # Iterative right boundary walk (reversed)
        temp = []
        curr = root.right
        while curr:
            if not is_leaf(curr):
                temp.append(curr.val)
            curr = curr.right if curr.right else curr.left
        result.extend(temp[::-1])
        
        return result

import java.util.*;

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        result.add(root.val);
        if (isLeaf(root)) return result;
        
        // Iterative left boundary walk
        TreeNode curr = root.left;
        while (curr != null) {
            if (!isLeaf(curr)) result.add(curr.val);
            curr = (curr.left != null) ? curr.left : curr.right;
        }
        
        // DFS for leaf nodes
        addLeaves(root, result);
        
        // Iterative right boundary walk (reversed)
        List<Integer> temp = new ArrayList<>();
        curr = root.right;
        while (curr != null) {
            if (!isLeaf(curr)) temp.add(curr.val);
            curr = (curr.right != null) ? curr.right : curr.left;
        }
        Collections.reverse(temp);
        result.addAll(temp);
        
        return result;
    }
    
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
    
    private void addLeaves(TreeNode node, List<Integer> result) {
        if (node == null) return;
        if (isLeaf(node)) {
            result.add(node.val);
            return;
        }
        addLeaves(node.left, result);
        addLeaves(node.right, result);
    }
}

Complexity Analysis

Time Complexity: O(n)

The left boundary while-loop visits at most h nodes (one per level along the leftmost path). The leaf DFS visits all n nodes exactly once. The right boundary while-loop visits at most h nodes. Total: O(h + n + h) = O(n + 2h) = O(n), since h ≤ n.

Space Complexity: O(h)

The leaf DFS recursion stack uses O(h) space in the worst case. The right boundary temporary list holds at most h values. No intermediate lists are created for the left boundary (values go directly into result). Total auxiliary space: O(h). For a balanced tree with n = 10,000 nodes, h ≈ 14, so we use only ~14 words of stack space instead of building multiple lists of thousands of elements.