Boundary Traversal of Binary Tree

Traverse the boundary of a binary tree in anti-clockwise direction.

Language Selection

Choose your preferred programming language

Showing: Python

Boundary Traversal of Binary Tree

Problem Statement

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.

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves, and the right boundary in order without duplicate nodes.

Examples

Example 1:

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

Explanation:
The boundary includes:
- Root: 1
- Left boundary: (empty)
- Leaves: 3, 4
- Right boundary: 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 boundary includes:
- Root: 1
- Left boundary: 2, 4
- Leaves: 7, 8, 9, 10
- Right boundary: 6, 3

Constraints

0 <= Number of nodes <= 10^4
-1000 <= Node.val <= 1000

Approach 1: Three-Step Boundary Traversal (Optimal)

Algorithm

Break down the boundary traversal into three parts:

Left boundary (excluding leaves)
Leaf nodes
Right boundary (excluding leaves, in reverse order)

Steps:

Add root to result
Add left boundary nodes (top to bottom)
Add leaf nodes (left to right)
Add right boundary nodes (bottom to top)

Implementation

Python:

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

def boundaryOfBinaryTree(root):
    """
    Boundary traversal of binary tree
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    if not root:
        return []
    
    result = []
    
    # Add root if it's not a leaf
    if not isLeaf(root):
        result.append(root.val)
    
    # Add left boundary
    addLeftBoundary(root.left, result)
    
    # Add leaves
    addLeaves(root, result)
    
    # Add right boundary
    addRightBoundary(root.right, result)
    
    return result

def isLeaf(node):
    """Check if node is a leaf"""
    return node and not node.left and not node.right

def addLeftBoundary(node, result):
    """Add left boundary nodes (excluding leaves)"""
    while node and not isLeaf(node):
        result.append(node.val)
        if node.left:
            node = node.left
        else:
            node = node.right

def addLeaves(node, result):
    """Add all leaf nodes"""
    if not node:
        return
    
    if isLeaf(node):
        result.append(node.val)
    else:
        addLeaves(node.left, result)
        addLeaves(node.right, result)

def addRightBoundary(node, result):
    """Add right boundary nodes (excluding leaves, in reverse order)"""
    stack = []
    while node and not isLeaf(node):
        stack.append(node.val)
        if node.right:
            node = node.right
        else:
            node = node.left
    
    # Add in reverse order
    while stack:
        result.append(stack.pop())

Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        
        if (root == null) {
            return result;
        }
        
        // Add root if it's not a leaf
        if (!isLeaf(root)) {
            result.add(root.val);
        }
        
        // Add left boundary
        addLeftBoundary(root.left, result);
        
        // Add leaves
        addLeaves(root, result);
        
        // Add right boundary
        addRightBoundary(root.right, result);
        
        return result;
    }
    
    private boolean isLeaf(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }
    
    private void addLeftBoundary(TreeNode node, List<Integer> result) {
        while (node != null && !isLeaf(node)) {
            result.add(node.val);
            if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
    }
    
    private void addLeaves(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        
        if (isLeaf(node)) {
            result.add(node.val);
        } else {
            addLeaves(node.left, result);
            addLeaves(node.right, result);
        }
    }
    
    private void addRightBoundary(TreeNode node, List<Integer> result) {
        Stack<Integer> stack = new Stack<>();
        while (node != null && !isLeaf(node)) {
            stack.push(node.val);
            if (node.right != null) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        
        // Add in reverse order
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
    }
}

Go:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func boundaryOfBinaryTree(root *TreeNode) []int {
    var result []int
    
    if root == nil {
        return result
    }
    
    // Add root if it's not a leaf
    if !isLeaf(root) {
        result = append(result, root.Val)
    }
    
    // Add left boundary
    addLeftBoundary(root.Left, &result)
    
    // Add leaves
    addLeaves(root, &result)
    
    // Add right boundary
    addRightBoundary(root.Right, &result)
    
    return result
}

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

func addLeftBoundary(node *TreeNode, result *[]int) {
    for node != nil && !isLeaf(node) {
        *result = append(*result, node.Val)
        if node.Left != nil {
            node = node.Left
        } else {
            node = node.Right
        }
    }
}

func addLeaves(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    
    if isLeaf(node) {
        *result = append(*result, node.Val)
    } else {
        addLeaves(node.Left, result)
        addLeaves(node.Right, result)
    }
}

func addRightBoundary(node *TreeNode, result *[]int) {
    var stack []int
    for node != nil && !isLeaf(node) {
        stack = append(stack, node.Val)
        if node.Right != nil {
            node = node.Right
        } else {
            node = node.Left
        }
    }
    
    // Add in reverse order
    for i := len(stack) - 1; i >= 0; i-- {
        *result = append(*result, stack[i])
    }
}

JavaScript:

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

function boundaryOfBinaryTree(root) {
    const result = [];
    
    if (!root) {
        return result;
    }
    
    // Add root if it's not a leaf
    if (!isLeaf(root)) {
        result.push(root.val);
    }
    
    // Add left boundary
    addLeftBoundary(root.left, result);
    
    // Add leaves
    addLeaves(root, result);
    
    // Add right boundary
    addRightBoundary(root.right, result);
    
    return result;
}

function isLeaf(node) {
    return node && !node.left && !node.right;
}

function addLeftBoundary(node, result) {
    while (node && !isLeaf(node)) {
        result.push(node.val);
        if (node.left) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
}

function addLeaves(node, result) {
    if (!node) {
        return;
    }
    
    if (isLeaf(node)) {
        result.push(node.val);
    } else {
        addLeaves(node.left, result);
        addLeaves(node.right, result);
    }
}

function addRightBoundary(node, result) {
    const stack = [];
    while (node && !isLeaf(node)) {
        stack.push(node.val);
        if (node.right) {
            node = node.right;
        } else {
            node = node.left;
        }
    }
    
    // Add in reverse order
    while (stack.length > 0) {
        result.push(stack.pop());
    }
}

C#:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public IList<int> BoundaryOfBinaryTree(TreeNode root) {
        List<int> result = new List<int>();
        
        if (root == null) {
            return result;
        }
        
        // Add root if it's not a leaf
        if (!IsLeaf(root)) {
            result.Add(root.val);
        }
        
        // Add left boundary
        AddLeftBoundary(root.left, result);
        
        // Add leaves
        AddLeaves(root, result);
        
        // Add right boundary
        AddRightBoundary(root.right, result);
        
        return result;
    }
    
    private bool IsLeaf(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }
    
    private void AddLeftBoundary(TreeNode node, List<int> result) {
        while (node != null && !IsLeaf(node)) {
            result.Add(node.val);
            if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
    }
    
    private void AddLeaves(TreeNode node, List<int> result) {
        if (node == null) {
            return;
        }
        
        if (IsLeaf(node)) {
            result.Add(node.val);
        } else {
            AddLeaves(node.left, result);
            AddLeaves(node.right, result);
        }
    }
    
    private void AddRightBoundary(TreeNode node, List<int> result) {
        Stack<int> stack = new Stack<int>();
        while (node != null && !IsLeaf(node)) {
            stack.Push(node.val);
            if (node.right != null) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        
        // Add in reverse order
        while (stack.Count > 0) {
            result.Add(stack.Pop());
        }
    }
}

Complexity Analysis

Time Complexity: O(n) - Visit each node once
Space Complexity: O(h) - Recursion stack depth

Key Insights

Three Components: Boundary = Root + Left Boundary + Leaves + Right Boundary
Anti-clockwise Order: Left boundary (top-down), leaves (left-right), right boundary (bottom-up)
No Duplicates: Avoid adding nodes multiple times
Leaf Handling: Special handling for leaf nodes
Edge Cases: Single node, skewed trees, empty trees

Edge Cases

Empty Tree: Return empty list
Single Node: Return [node.val]
Left Skewed: Only left boundary and leaves
Right Skewed: Only right boundary and leaves
Complete Tree: All three components present

Follow-up Questions

Clockwise Boundary: How would you traverse boundary in clockwise direction?
Inner Boundary: Find the boundary of inner nodes (excluding leaves)?
Kth Boundary: Find nodes at distance k from boundary?
Boundary Sum: Calculate sum of all boundary nodes?
Boundary Validation: Check if a tree has valid boundary structure?

Common Mistakes

Duplicate Nodes: Adding same node multiple times
Order Confusion: Wrong order for right boundary (should be bottom-up)
Leaf Handling: Not properly identifying leaf nodes
Root Handling: Adding root when it’s a leaf
Edge Cases: Not handling single node or empty tree

Interview Tips

Clarify Requirements: Ask about duplicate handling and order
Discuss Approaches: Mention both three-step and single DFS approaches
Handle Edge Cases: Discuss empty tree, single node scenarios
Explain Algorithm: Walk through the three components clearly
Consider Optimizations: Discuss space and time tradeoffs