DSA 450 Notes

Problem Statement

Given a binary tree, print the boundary nodes of the tree anti-clockwise starting from the root. The boundary includes: left boundary (excluding leaves), all leaves (left to right), and right boundary (excluding leaves, in reverse).

Example:

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

Root: 1
Left boundary (excl leaves): 2
Leaves (L to R): 4, 7, 8, 6
Right boundary (excl leaves, reverse): 3

Approach 1: Three-Part Traversal

Intuition

Break the problem into three parts:

Left boundary: Go left, add non-leaf nodes
Leaves: Inorder traversal, add only leaves
Right boundary: Go right, add non-leaf nodes in reverse

Algorithm

Add root (if not leaf)
Traverse left boundary (prefer left child, else right, stop at leaf)
Add all leaves using inorder traversal
Traverse right boundary in reverse (prefer right child, else left)

java

import java.util.*;

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

public class Solution {
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
    
    private void addLeftBoundary(TreeNode root, List<Integer> result) {
        TreeNode curr = root.left;
        while (curr != null) {
            if (!isLeaf(curr)) {
                result.add(curr.val);
            }
            // Prefer left, else go right
            if (curr.left != null) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
    }
    
    private void addLeaves(TreeNode root, List<Integer> result) {
        if (root == null) return;
        
        if (isLeaf(root)) {
            result.add(root.val);
            return;
        }
        
        addLeaves(root.left, result);
        addLeaves(root.right, result);
    }
    
    private void addRightBoundary(TreeNode root, List<Integer> result) {
        TreeNode curr = root.right;
        List<Integer> temp = new ArrayList<>();
        
        while (curr != null) {
            if (!isLeaf(curr)) {
                temp.add(curr.val);
            }
            // Prefer right, else go left
            if (curr.right != null) {
                curr = curr.right;
            } else {
                curr = curr.left;
            }
        }
        
        // Add in reverse order
        for (int i = temp.size() - 1; i >= 0; i--) {
            result.add(temp.get(i));
        }
    }
    
    public List<Integer> boundaryTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        // Add root if not a leaf
        if (!isLeaf(root)) {
            result.add(root.val);
        }
        
        // Add left boundary
        addLeftBoundary(root, result);
        
        // Add leaves
        addLeaves(root, result);
        
        // Add right boundary (reverse)
        addRightBoundary(root, result);
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n) - Each node visited at most twice (boundary + leaves)
Space Complexity: O(n) - Result array and recursion stack

Approach 2: Single Pass with Flags

Intuition

Use DFS with flags to indicate whether a node is on left boundary, right boundary, or a leaf.

Algorithm

Track if we're on left boundary (first left path from root)
Track if we're on right boundary (first right path from root)
Process left boundary and leaves during forward pass
Process right boundary during backtrack

java

import java.util.*;

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

public class Solution {
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
    
    private void dfs(TreeNode node, boolean isLeftBoundary, boolean isRightBoundary,
                     List<Integer> result) {
        if (node == null) return;
        
        // Add to result if on left boundary or is a leaf
        if (isLeftBoundary || isLeaf(node)) {
            result.add(node.val);
        }
        
        // Recurse on left child
        dfs(node.left,
            isLeftBoundary,
            isRightBoundary && node.right == null,
            result);
        
        // Recurse on right child
        dfs(node.right,
            isLeftBoundary && node.left == null,
            isRightBoundary,
            result);
        
        // Add right boundary nodes during backtrack
        if (isRightBoundary && !isLeaf(node) && !isLeftBoundary) {
            result.add(node.val);
        }
    }
    
    public List<Integer> boundaryTraversalSinglePass(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        result.add(root.val);
        
        if (isLeaf(root)) return result;
        
        dfs(root.left, true, false, result);
        dfs(root.right, false, true, result);
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n) - Each node visited once
Space Complexity: O(n) - Recursion stack

Key Takeaways

Boundary = Left boundary + Leaves + Right boundary (reversed)
Three-part approach is easier to understand and implement
Single-pass approach is elegant but harder to debug
Key edge cases: Root is leaf, tree has only left/right subtree
Left boundary: Go left when possible, else right (exclude leaves)
Right boundary: Go right when possible, else left (exclude leaves, reverse order)
Leaves are collected using any traversal that visits left before right

Boundary traversal of a Binary tree

Problem Statement

Approach 1: Three-Part Traversal

Intuition

Algorithm

Complexity Analysis

Approach 2: Single Pass with Flags

Intuition

Algorithm

Complexity Analysis

Key Takeaways