Binary Tree Traversal and Fundamental Operations

Definition of a Binary Tree

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child.

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

          1          ← Root Node
         / \
        2   3        ← Level 2
       / \   \
      4   5   6      ← Level 3 (Leaf Nodes)

Common Terminology:

• Root: The top node of the tree (has no parent).
• Leaf: A node with no children.
• Height: The number of edges on the longest path from the root to a leaf.
• Depth: The number of edges from the root to a specific node.

Depth-First Search (DFS) Traversal

There are three primary orders for DFS traversal, defined by when the root node is visited relative to its children:

Recursive Implementation (Simplest)

// Pre-order: Root -> Left -> Right
void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(root.val);        // Process Root
    preorder(root.left, result);
    preorder(root.right, result);
}

// In-order: Left -> Root -> Right
void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    inorder(root.left, result);
    result.add(root.val);        // Process Root
    inorder(root.right, result);
}

// Post-order: Left -> Right -> Root
void postorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);        // Process Root
}

Recursion Principle: The function call stack facilitates the traversal. Each call corresponds to a "push" onto the stack, and return corresponds to a "pop."

Iterative Implementation (Pre-order, using Explicit Stack)

List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // Push right first so that left is processed first (LIFO stack behavior)
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

In-order Iterative (Crucial for BST Problems)

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        // 1. Traverse all the way to the leftmost node, pushing each along the way
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        // 2. Pop the leftmost node (the current minimum/next value)
        cur = stack.pop();
        result.add(cur.val);
        // 3. Move to the right subtree
        cur = cur.right;
    }
    return result;
}

Level-Order Traversal (BFS)

BFS visits nodes level by level using a queue.

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size(); // Number of nodes at the current level
        List<Integer> currentLevel = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(currentLevel);
    }
    return result;
}

Tree Height and Depth

// Maximum Depth (Height) of a binary tree
// Time: O(n), Space: O(h) where h is the tree height
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Minimum Depth (Shortest path to any leaf node)
int minDepth(TreeNode root) {
    if (root == null) return 0;
    // Base case: Leaf node
    if (root.left == null && root.right == null) return 1;
    // If one child is null, only search the other path
    if (root.left == null) return 1 + minDepth(root.right);
    if (root.right == null) return 1 + minDepth(root.left);
    
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

Binary Search Tree (BST)

A BST is an ordered binary tree where for every node: All left subtree nodes < Root < All right subtree nodes.

Key Property: An in-order traversal of a BST yields a strictly increasing sequence.

// BST Search (Exploits order, O(h) time, O(log n) if balanced)
TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return search(root.left, target);
    return search(root.right, target);
}

// Validating a BST: Use in-order iteration to ensure strict progression
boolean isValidBST(TreeNode root) {
    long prev = Long.MIN_VALUE; // Used to prevent int overflow issues
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (cur.val <= prev) return false; // Must be strictly increasing
        prev = cur.val;
        cur = cur.right;
    }
    return true;
}

Path and Subtree Problems

Path Sum

// Detect if there exists a root-to-leaf path summing to target
boolean hasPathSum(TreeNode root, int target) {
    if (root == null) return false;
    // Leaf node check
    if (root.left == null && root.right == null) return root.val == target;
    
    return hasPathSum(root.left, target - root.val) 
        || hasPathSum(root.right, target - root.val);
}

Symmetric Tree

boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode l, TreeNode r) {
    if (l == null && r == null) return true;
    if (l == null || r == null) return false;
    
    return (l.val == r.val)
        && isMirror(l.left, r.right)  // Outer symmetry
        && isMirror(l.right, r.left); // Inner symmetry
}

Recursive Mental Model

When solving tree problems, ask yourself:

1. What is my role (at the current node)?
2. What information do I need from my subtrees?
3. What result should I return to my parent?

Most tree problems follow one of two patterns:

Pattern 1: Traversal (Global State)

void traverse(TreeNode root) {
    if (root == null) return;
    // Pre-order Position: Act on current node (e.g. record into global list)
    traverse(root.left);
    // In-order Position
    traverse(root.right);
    // Post-order Position: Ability to act using info passed up from children
}

Pattern 2: Decomposition (Dependency on Return Values)

int solve(TreeNode root) {
    if (root == null) return 0;           // Base Case
    int leftResult = solve(root.left);    // Collect from left
    int rightResult = solve(root.right);  // Collect from right
    // Derive current node result using child results
    return root.val + Math.max(leftResult, rightResult); 
}

Summary

Refactoring Tree Problems Checklist:

1. Decide: Traversing vs Decompressing?
2. Identify the Return Value: What must children tell the parent?
3. Define Base Cases: What happens at null or leaf?
4. Write Root Logic: How is the final result assembled?