Tree Traversals in Java: Mastering BFS and DFS for Coding Interviews

Introduction to Tree Traversals

Trees are foundational data structures in computer science, representing hierarchical relationships. Unlike arrays or linked lists, which are linear, trees have multiple "paths" you can follow. To solve problems involving trees, you must know how to visit every node systematically. This is where Tree Traversals come in.

The two fundamental ways to traverse a tree are Breadth-First Search (BFS) and Depth-First Search (DFS). Mastering these two patterns is non-negotiable for FAANG interviews, as they form the basis for almost all tree and graph problems.

1. Breadth-First Search (BFS) Pattern

Breadth-First Search explores the tree level by level. It starts at the root, visits all nodes at depth 1, then all nodes at depth 2, and so on.

When to use BFS

You need to traverse the tree level-by-level.
You are looking for the shortest path in an unweighted graph or tree.
The problem asks for the "minimum depth" or "right-side view" of a tree.

Core Concept: The Queue

BFS relies heavily on a Queue (First-In, First-Out) data structure. We push the root into the queue, and then enter a loop: pop a node, process it, and push its children into the queue.

Example: Binary Tree Level Order Traversal

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).

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

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

class Solution {
    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()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            // Process all nodes at the current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                // Add children to the queue for the next level
                if (currentNode.left != null) queue.offer(currentNode.left);
                if (currentNode.right != null) queue.offer(currentNode.right);
            }
            result.add(currentLevel);
        }
        return result;
    }
}

Complexity:

Time Complexity: $O(n)$, where $n$ is the number of nodes. We visit each node exactly once.
Space Complexity: $O(n)$. In the worst case (a perfectly balanced tree), the queue will hold all nodes at the lowest level, which is roughly $n/2$ nodes.

2. Depth-First Search (DFS) Pattern

Depth-First Search explores as far down a single branch as possible before backtracking. It dives deep into the leaves before visiting siblings.

When to use DFS

You need to traverse a tree branch-by-branch (e.g., path sum problems).
You are looking for all possible paths or combinations.
You need to validate binary search tree (BST) properties.

Core Concept: Recursion or Stack

DFS naturally maps to Recursion because exploring a tree is a recursive task (a tree is a node with subtrees). If done iteratively, it requires a Stack (Last-In, First-Out).

DFS has three common variations based on when we process the current node:

Pre-order: Process node $\rightarrow$ Left subtree $\rightarrow$ Right subtree
In-order: Left subtree $\rightarrow$ Process node $\rightarrow$ Right subtree (Returns sorted values for a BST)
Post-order: Left subtree $\rightarrow$ Right subtree $\rightarrow$ Process node

Example: Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Recursive DFS Approach

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Base case: empty node
        if (root == null) return false;

        // Base case: leaf node
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        // Recursive step: subtract current node's value from targetSum
        return hasPathSum(root.left, targetSum - root.val) || 
               hasPathSum(root.right, targetSum - root.val);
    }
}

Complexity:

Time Complexity: $O(n)$, where $n$ is the number of nodes. We might have to visit every node.
Space Complexity: $O(h)$, where $h$ is the height of the tree. This is due to the recursion stack. In the worst case (a skewed tree), it's $O(n)$. In a balanced tree, it's $O(\log n)$.

Iterative DFS Approach (Pre-order using Stack)

import java.util.Stack;

class Solution {
    public boolean hasPathSumIterative(TreeNode root, int targetSum) {
        if (root == null) return false;

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();

        nodeStack.push(root);
        sumStack.push(targetSum - root.val);

        while (!nodeStack.isEmpty()) {
            TreeNode currentNode = nodeStack.pop();
            int currentSum = sumStack.pop();

            // Check if it's a leaf and the sum matches
            if (currentNode.left == null && currentNode.right == null && currentSum == 0) {
                return true;
            }

            // Push right child first so left is processed first (Pre-order)
            if (currentNode.right != null) {
                nodeStack.push(currentNode.right);
                sumStack.push(currentSum - currentNode.right.val);
            }
            if (currentNode.left != null) {
                nodeStack.push(currentNode.left);
                sumStack.push(currentSum - currentNode.left.val);
            }
        }
        return false;
    }
}

How to Recognize BFS vs DFS in Interviews

"Shortest Path" or "Levels": Use BFS.
"All Paths", "Combinations", or "Backtracking": Use DFS.
"Valid BST" or "In-order properties": Use DFS (In-order).
When memory is a massive constraint and the tree is very wide but not deep, DFS is preferred. If the tree is very deep but not wide, BFS might save stack space.

Common Mistakes

Mistake 1: Not tracking the level size in BFS

In problems like "Right Side View" or "Level Order Traversal", you must capture int levelSize = queue.size(); before entering the inner loop. If you rely on queue.size() directly in the loop condition (i < queue.size()), it will change dynamically as you add children, breaking the level boundaries.

Mistake 2: Missing the leaf node check in DFS path problems

A path is strictly "root-to-leaf". Simply checking if (root == null && targetSum == 0) will incorrectly return true for a node that only has one child (since the missing child's null pointer will trigger the check). You must explicitly check if (root.left == null && root.right == null).

Example 3: Binary Tree Maximum Path Sum

Find the maximum path sum in a binary tree. A path can start and end at any node.

int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    calculateGain(root);
    return maxSum;
}
private int calculateGain(TreeNode node) {
    if (node == null) return 0;
    int leftGain = Math.max(calculateGain(node.left), 0);
    int rightGain = Math.max(calculateGain(node.right), 0);
    maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
    return node.val + Math.max(leftGain, rightGain);
}

Example 4: Lowest Common Ancestor

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Practice Problems

Binary Tree Level Order Traversal: (Easy)
Binary Tree Right Side View: (Medium)
Maximum Depth of Binary Tree: (Easy)
Path Sum: (Easy)
Path Sum II: Return all root-to-leaf paths that sum to target. (Medium)
Lowest Common Ancestor of a Binary Tree: (Medium)
Binary Tree Zigzag Level Order Traversal: (Medium)
Serialize and Deserialize Binary Tree: (Hard)
Diameter of Binary Tree: (Easy)
Validate Binary Search Tree: (Medium)

Interview Script You Can Reuse

For BFS:

"Since we need to process the tree level by level (or find the shortest path), Breadth-First Search is the best approach. I'll use a Queue to keep track of the nodes at the current depth. I'll take the size of the queue at the start of each iteration to ensure I only process nodes belonging to the current level before moving deeper. This will give an O(n) time complexity and O(w) space complexity, where w is the maximum width of the tree."

For DFS:

"Because we need to explore paths from the root to the leaves, Depth-First Search is appropriate. I'll use a recursive helper function (or a Stack) to traverse down the branches. At each step, I'll pass down the accumulated state (like the remaining path sum). The time complexity will be O(n) to visit all nodes, and the space complexity will be O(h) for the recursion stack, where h is the tree height."

Final Takeaways

BFS uses a Queue and explores level-by-level. Ideal for shortest path or level-wise operations.
DFS uses Recursion (or a Stack) and explores branch-by-branch. Ideal for path finding, combinations, and validations.
Always be mindful of the levelSize in BFS and leaf node base cases in DFS.