Difficulty: Medium
Category: Tree, DFS, Binary Tree
Companies: Amazon, Google, Facebook, Microsoft

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.

Left boundary is defined as the path from root to the left-most node. If the root doesn’t have a left subtree, then the left boundary is empty.

Right boundary is defined as the path from root to the right-most node. If the root doesn’t have a right subtree, then the right boundary is empty.

Left-most node is the leaf node you reach when you always travel to the left subtree if it exists. If not, travel to the right subtree. Stop when you reach a leaf node.

Right-most node is the leaf node you reach when you always travel to the right subtree if it exists. If not, travel to the left subtree. Stop when you reach a leaf node.

Leaf nodes are nodes that don’t have any children.

Examples

Example 1:

Input: root = [1,null,2,3,4]
Output: [1,3,4,2]
Explanation:
- The left boundary is empty because the root doesn't have a left child.
- The right boundary follows the path 1 -> 2 -> 4.
- The leaves from left to right are 3, 4.
- The anti-clockwise boundary is [1,3,4,2].

Example 2:

Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
Output: [1,2,4,7,8,9,10,6,3]
Explanation:
- The left boundary follows the path 1 -> 2 -> 4.
- The right boundary follows the path 1 -> 3 -> 6.
- The leaves from left to right are 4, 7, 8, 9, 10.
- The anti-clockwise boundary is [1,2,4,7,8,9,10,6,3].

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Key Insight

The boundary traversal consists of three parts in order:

  1. Left boundary: Root → leftmost node (excluding leaves)
  2. Leaves: All leaf nodes from left to right
  3. Right boundary: Rightmost node → root (excluding leaves, in reverse order)

Approach: Three-Step Boundary Traversal

Algorithm:

  1. Add root to result (if not a leaf)
  2. Traverse left boundary (excluding leaves)
  3. Traverse all leaves from left to right
  4. Traverse right boundary (excluding leaves, in reverse order)

Time Complexity: O(n)
Space Complexity: O(h) where h is height of tree

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

        result = []

        # root (only if not leaf)
        if not self.isLeaf(root):
            result.append(root.val)

        # left boundary
        self.getLeft(root.left, result)

        # leaves
        self.getLeaves(root, result)

        # right boundary
        right = []
        self.getRight(root.right, right)
        result.extend(reversed(right))

        return result

    def isLeaf(self, node):
        return node and not node.left and not node.right

    def getLeft(self, node, res):
        while node:
            if not self.isLeaf(node):
                res.append(node.val)
            node = node.left if node.left else node.right

    def getRight(self, node, res):
        while node:
            if not self.isLeaf(node):
                res.append(node.val)
            node = node.right if node.right else node.left

    def getLeaves(self, node, res):
        if not node:
            return
        if self.isLeaf(node):
            res.append(node.val)
            return
        self.getLeaves(node.left, res)
        self.getLeaves(node.right, res)

Alternative Approach: Single Pass with Flags

Algorithm:

  1. Use flags to track if a node is on left boundary, right boundary, or is a leaf
  2. Traverse the tree once and collect nodes based on flags
  3. Handle special cases for root and single-node trees
class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> list[int]:
        if not root:
            return []

        result = []

        if not self.isLeaf(root):
            result.append(root.val)

        # left boundary
        self.getLeftBoundary(root.left, result)

        # leaves
        self.getLeaves(root, result)

        # right boundary
        right = []
        self.getRightBoundary(root.right, right)
        result.extend(reversed(right))

        return result

    def isLeaf(self, node):
        return node and not node.left and not node.right

    def getLeftBoundary(self, node, res):
        while node:
            if not self.isLeaf(node):
                res.append(node.val)
            node = node.left if node.left else node.right

    def getRightBoundary(self, node, res):
        while node:
            if not self.isLeaf(node):
                res.append(node.val)
            node = node.right if node.right else node.left

    def getLeaves(self, node, res):
        if not node:
            return

        if self.isLeaf(node):
            res.append(node.val)
            return

        self.getLeaves(node.left, res)
        self.getLeaves(node.right, res)
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Detailed Algorithm Breakdown

1. Left Boundary Traversal

  • Start from root’s left child
  • Always prefer left child if exists, otherwise go right
  • Stop when reaching a leaf node
  • Add nodes to result during traversal

2. Leaf Traversal

  • Perform inorder traversal to get leaves from left to right
  • Add only leaf nodes (nodes with no children)
  • Skip non-leaf nodes

3. Right Boundary Traversal

  • Start from root’s right child
  • Always prefer right child if exists, otherwise go left
  • Stop when reaching a leaf node
  • Add nodes to result after recursive calls (reverse order)

Edge Cases Handling

  1. Empty Tree: Return empty vector
  2. Single Node: Return [root->val]
  3. Root is Leaf: Only add root once
  4. No Left/Right Subtree: Handle gracefully in boundary functions

Complexity

| Aspect | Complexity | Explanation | |——–|————|————-| | Time | O(n) | Visit each node exactly once | | Space | O(h) | Recursion stack depth equals tree height |

Key Implementation Details

  1. Leaf Check: !node->left && !node->right
  2. Boundary Logic: Prefer left/right child, fallback to other child
  3. Order Matters: Left boundary → Leaves → Right boundary (reversed)
  4. Duplicate Prevention: Each node appears exactly once in result

Follow-up Questions

  • What if we need the boundary in clockwise direction?
  • How would you handle duplicate values in the tree?
  • What if we need to find the boundary of a general tree (not binary)?

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Implementation Notes

  1. Recursive Approach: Clean and intuitive implementation
  2. Boundary Detection: Use child existence to determine boundary
  3. Order Preservation: Maintain anti-clockwise order throughout
  4. Memory Efficiency: O(h) space complexity for balanced trees

Key Takeaways

  • Algorithm:**
  • Time Complexity:** O(n)
  • Space Complexity:** O(h) where h is height of tree

References

Template Reference