Binary Tree Traversal (Recursion, Iteration, BFS Layer)

Recursive Traversals

The three depth-first orders depend on the placement of the root node relative to children:

class TreeNode { int val; TreeNode left, right; }

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

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

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

Iterative Traversals (High Frequency)

Pre-order Iteration

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

In-order Iteration

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        // Traverse all the way to the leftmost node
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        res.add(cur.val);
        cur = cur.right; // Switch to right subtree
    }
    return res;
}

Post-order Iteration

By reversing the logic of pre-order (Root-Right-Left) and inserting at the head, we achieve (Left-Right-Root):

List<Integer> postorderIterative(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>(); 
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val); // Root -> Left -> Right logic reversed by addFirst
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}

Level-Order Traversal (BFS, LeetCode 102)

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size(); // Capture number of nodes at this level
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

BFS Variations

• Zigzag Level Order (LeetCode 103): Toggle a flag and use level.addFirst(node.val) for every other level.
• Maximum Width (LeetCode 662): Assign index i to root, 2i to left, and 2i + 1 to right. Width is rightmost_index - leftmost_index + 1 within each level.

Binary Tree Properties

// Maximum Depth
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Balanced Check (l/r subtree height difference <= 1)
int checkHeight(TreeNode root) {
    if (root == null) return 0;
    int left = checkHeight(root.left);
    if (left == -1) return -1;
    int right = checkHeight(root.right);
    if (right == -1) return -1;
    
    return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
boolean isBalanced(TreeNode root) { return checkHeight(root) != -1; }

// Symmetric Check (LeetCode 101)
boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}
boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return (a.val == b.val) 
        && isMirror(a.left, b.right) 
        && isMirror(a.right, b.left);
}