Tree Traversals

1. Introduction: Walking the Tree

In an Array, there is only one logical way to traverse: left to right. In a Binary Tree, because every node branches in two directions, there are multiple ways to traverse the data. Do you read the parent first, or the children first? Do you read left-to-right, or top-to-bottom?

The ability to write the four foundational Tree Traversals—Pre-Order, In-Order, Post-Order, and Level-Order—from memory is a mandatory prerequisite for any software engineering interview. If you stumble on these, the interview is over.

2. Core Concept: Depth-First vs Breadth-First

Tree traversals are divided into two massive families:

1. Depth-First Search (DFS): Dive as deep as possible down a branch until you hit a leaf, then backtrack. DFS is naturally implemented using Recursion (which uses the OS Call Stack).

   • Pre-Order: Current Node, Left Child, Right Child. (Used for copying/serializing trees).
   • In-Order: Left Child, Current Node, Right Child. (Used for flattening BSTs into sorted arrays).
   • Post-Order: Left Child, Right Child, Current Node. (Used for deleting trees or calculating heights).

2. Breadth-First Search (BFS): Read the tree level by level, top to bottom, left to right. BFS is naturally implemented iteratively using a Queue.

   • Level-Order: Process depth 0, then depth 1, then depth 2. (Used for finding the shortest path).

3. Beginner Code Example: The 3 DFS Traversals (Recursive)

Problem Statement: (LeetCode 94, 144, 145) Return a list of the tree node values based on a specific traversal order.

The Insight: The code for all three DFS traversals is exactly the same! The ONLY difference is where you place the result.add(node.val) line.

import java.util.ArrayList;
import java.util.List;

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

public class DFSTraversals {
    
    // 1. PRE-ORDER (Node -> Left -> Right)
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }
    private void preorder(TreeNode node, List<Integer> res) {
        if (node == null) return;
        res.add(node.val);          // 1. Process Node FIRST
        preorder(node.left, res);   // 2. Go Left
        preorder(node.right, res);  // 3. Go Right
    }
    
    // 2. IN-ORDER (Left -> Node -> Right)
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    private void inorder(TreeNode node, List<Integer> res) {
        if (node == null) return;
        inorder(node.left, res);    // 1. Go Left
        res.add(node.val);          // 2. Process Node IN THE MIDDLE
        inorder(node.right, res);   // 3. Go Right
    }
    
    // 3. POST-ORDER (Left -> Right -> Node)
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    private void postorder(TreeNode node, List<Integer> res) {
        if (node == null) return;
        postorder(node.left, res);  // 1. Go Left
        postorder(node.right, res); // 2. Go Right
        res.add(node.val);          // 3. Process Node LAST
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We visit every node exactly once.
• Space Complexity: $O(H)$ for the call stack, where $H$ is tree height.

4. Intermediate Code Example: Level-Order Traversal (BFS)

Problem Statement: (LeetCode 102) Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Output format: List<List<Integer>>.

The Insight: Recursion naturally goes deep. To go wide, we must use a Queue. We push the root in. Then, we write a while loop that processes everything currently in the queue, pushing their children to the back of the queue for the next level.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFSTraversal {
    public 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()) {
            // SNAPSHOT: The current size of the queue is EXACTLY the number of nodes on this level!
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            // Process exactly 'levelSize' nodes. 
            // Any children added during this loop will just wait at the back of the queue for the next while-loop iteration!
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                // Enqueue children (left to right)
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            // Add the completed level to the final result
            result.add(currentLevel);
        }
        
        return result;
    }
}

5. Advanced Code Example: Iterative In-Order Traversal

In rare cases, interviewers might ban recursion. To simulate In-Order DFS without the OS Call Stack, you must manually manage a java.util.Stack.

The Insight: In-Order means we must process the far-left node first. So we push the root onto the stack, and immediately dive left, pushing every node we see until we hit null. Then we pop a node, process it, and step right exactly once. Repeat!

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class IterativeInorder {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            // 1. Dive as far left as mathematically possible
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            
            // 2. We hit null. Pop the top node (the leftmost available)
            curr = stack.pop();
            
            // 3. PROCESS THE NODE
            result.add(curr.val);
            
            // 4. Step to the right exactly once (it might be null, which is fine!)
            curr = curr.right;
        }
        
        return result;
    }
}

6. Common Mistakes Beginners Make

1. Forgetting levelSize in BFS

   • The Mistake: while(!q.isEmpty()) { TreeNode n = q.poll(); res.add(n); if(n.left!=null) q.offer(n.left); ... }
   • Why it's wrong: If the problem asks you to group the nodes by level (e.g. List<List<Integer>>), a basic while loop will just spit out a flat 1D array. You MUST capture int size = queue.size() before processing the level, and use a for (i=0 to size) loop to perfectly bound the current level.

2. Crashing on Null Roots

   • The Mistake: Writing BFS as queue.offer(root); while(!q.isEmpty()){ ... } without checking if root == null.
   • Why it's wrong: Queue.offer(null) is perfectly legal in Java LinkedList. The queue size will be 1! Inside the loop, node.val will immediately throw a NullPointerException. Always guard your tree functions with if (root == null) return;.

7. Interview Q&A

Q1: If you print a Binary Search Tree (BST) using In-Order traversal, what happens? Answer: The output will be perfectly sorted in ascending order! This is the most important property of a BST. If you want descending order, you do Reverse In-Order (Right -> Node -> Left).

Q2: Can you reconstruct a tree from a single Traversal output? Answer: No. If I give you Pre-Order [1, 2, 3], it could be 1 with left child 2 with left child 3, OR 1 with right child 2... etc. However, if you have TWO traversals (e.g., Pre-Order AND In-Order), you can perfectly mathematically reconstruct the exact tree! (LeetCode 105).

Q3: What is Morris Traversal? Answer: It is an elite algorithm that achieves In-Order traversal in $O(N)$ time and $O(1)$ space (no recursion stack, no manual stack). It does this by temporarily modifying the leaf nodes' right pointers to loop back up to their parents (creating a threaded tree), and restoring them later. It is rarely expected in interviews but gets massive bonus points.

8. Practice Problems

1. Binary Tree Inorder Traversal (LeetCode 94)
   • Goal: Write both the Recursive and Iterative versions flawlessly.
2. Binary Tree Level Order Traversal (LeetCode 102)
   • Goal: Master the Queue + levelSize BFS pattern.
3. Binary Tree Right Side View (LeetCode 199)
   • Hint: Do a Level-Order Traversal. At every level, only add the very last element (when i == levelSize - 1) to your final result array!

9. Summary

• DFS (Recursion): Dives deep.
  • Pre: Top-Down. In: Left-to-Right. Post: Bottom-Up.
• BFS (Queue): Scans wide.
  • Snapshot the size to process level-by-level.
• Iterative DFS: Use a Stack.