Mastering Depth First Search (DFS) in Binary Trees: Core Patterns and Problems

Depth First Search (DFS) is a fundamental tree traversal pattern that explores as deep as possible along each branch before backtracking. This guide covers the core mechanics of recursive DFS, demonstrating how to apply it to solve classic binary tree problems: inverting a tree, summing left leaf nodes, validating path sums, and checking height balance.

1. The Core Mental Model of Depth First Search (DFS)

Depth First Search (DFS) is a traversal strategy that prioritizes depth over breadth. When applied to binary trees, DFS utilizes the call stack (either implicitly via recursion or explicitly with an iterative stack) to plunge down to a leaf node before returning to process alternative branches.

The Recursive Call Stack Mechanics

In a recursive DFS, each function call is pushed onto the execution stack. The program state—including local variables and the current node pointer—is preserved. Once a base case is hit (typically encountering a null node), the function returns, popping the top frame off the stack and resuming execution in the parent frame.

Real-Life Analogy: Exploring a Maze

Imagine exploring a maze with branching paths. Instead of checking every path near the entrance first (which is Breadth First Search), you choose a path and walk as far as you can until you hit a dead end. Only when you cannot go any further do you backtrack to the last intersection to try a different path. This "go deep first, backtrack later" strategy is the essence of DFS.

2. Problem 1: Inverting a Binary Tree

Inverting a binary tree (often referred to as mirroring a tree) requires swapping the left and right children of every single node across the entire tree structure.

Visualizing the Swap

Consider the following binary tree:

        4
      /   \
     2     7
    / \   / \
   1   3 6   9

To invert this tree, we swap the left and right subtrees at every level, starting from the bottom up or top down. The resulting inverted tree looks like this:

        4
      /   \
     7     2
    / \   / \
   9   6 3   1

The Swapping Workflow

For any given node, the inversion process follows a simple three-step sequence:

1. Store the left child in a temporary variable.
2. Assign the right child to the left child pointer.
3. Assign the temporary variable (original left child) to the right child pointer.
4. Recursively repeat this process for both subtrees.

3. Code Evolution for Inverting a Binary Tree

We can implement this cleanly in Java using a recursive DFS approach. The algorithm visits each node exactly once and swaps its pointers.

Java Implementation

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        // Base Case: If the node is null, return null
        if (root == null) {
            return null;
        }

        // Swap the left and right children using a temporary variable
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert the left and right subtrees
        invertTree(root.left);
        invertTree(root.right);

        // Return the root of the inverted tree
        return root;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the total number of nodes in the tree. We must visit every node exactly once to perform the swap.
• Space Complexity: $\mathcal{O}(H)$, where $H$ is the height of the tree. This space is consumed by the recursive call stack.
  • In a balanced tree, the height is $\mathcal{O}(\log N)$.
  • In a skewed tree (worst-case scenario), the height is $\mathcal{O}(N)$.

4. Problem 2: Sum of Left Leaves

This problem requires us to calculate the sum of all leaf nodes that are specifically left children of their parent nodes.

Defining a "Left Leaf"

A node is classified as a left leaf if and only if it satisfies three strict conditions:

1. It is the immediate left child of its parent node.
2. It has no left child (node.left == null).
3. It has no right child (node.right == null).

        3
       / \
      9  20
        /  \
       15   7

In the tree above:

• Node 9 is a left child of 3 and has no children. (Left Leaf - Counted)
• Node 15 is a left child of 20 and has no children. (Left Leaf - Counted)
• Node 7 is a right child of 20. (Not a Left Leaf - Ignored)
• Total Sum: $9 + 15 = 24$.

5. Code Implementation for Sum of Left Leaves

To solve this, we traverse the tree. At each node, we look ahead to check if its left child is a leaf node. If it is, we capture its value and recursively search the right subtree. If it is not, we recursively search both subtrees.

Java Implementation

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int sum = 0;

        // Check if the left child is a leaf node
        if (root.left != null) {
            if (root.left.left == null && root.left.right == null) {
                // Root.left is a valid left leaf
                sum += root.left.val;
            }
        }

        // Recursively accumulate left leaf sums from left and right subtrees
        sum += sumOfLeftLeaves(root.left);
        sum += sumOfLeftLeaves(root.right);

        return sum;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ because we must traverse every node to check its children.
• Space Complexity: $\mathcal{O}(H)$ due to the recursive call stack, where $H$ is the height of the tree.

6. Problem 3: Path Sum

Given the root of a binary tree and a targetSum, determine if there exists a complete path from the root to any leaf node such that adding up all the values along the path equals targetSum.

The Target Reduction Pattern

Instead of maintaining a running sum variable as we travel down the tree, a cleaner approach is to subtract the current node's value from the targetSum at each step.

Mental Hook: Reducing a Debt Think of the targetSum as a debt you need to pay off. Every time you visit a node, you pay off a portion of the debt equal to that node's value. When you reach a leaf node, your remaining debt must be exactly equal to the leaf node's value (reducing the debt to exactly $0$).

Target Sum: 22

       5  (Remaining: 22 - 5 = 17)
      /
     4    (Remaining: 17 - 4 = 13)
    /
   11     (Remaining: 13 - 11 = 2)
  /  \
 7    2   (Leaf node '2' matches remaining target '2'. Path found!)

7. Code Implementation for Path Sum

The recursive function returns a boolean value. If we find a valid root-to-leaf path in either the left or right subtree, we propagate true back up the call stack.

Java Implementation

public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Base Case 1: Empty node cannot have a path
        if (root == null) {
            return false;
        }

        // Base Case 2: If we are at a leaf node, check if its value matches the remaining target
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        // Subtract current node's value and recursively check left and right subtrees
        int remainingSum = targetSum - root.val;
        boolean leftPath = hasPathSum(root.left, remainingSum);
        boolean rightPath = hasPathSum(root.right, remainingSum);

        // If either path returns true, then a valid path exists
        return leftPath || rightPath;
    }
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ in the worst case, as we may need to visit all nodes if no valid path exists or if the path is at the very end of our traversal.
• Space Complexity: $\mathcal{O}(H)$ to maintain the recursion stack.

8. Problem 4: Balanced Binary Tree

A binary tree is defined as height-balanced if:

For every node in the tree, the absolute difference between the height of its left subtree and the height of its right subtree is at most 1.

The Naive $O(N^2)$ Approach

A naive approach calculates the maximum depth of the left and right subtrees for every node in the tree.

       1
      / \
     2   3
    /
   4

1. At node 1, calculate height of left subtree (2) and right subtree (1). Difference is $1 \le 1$.
2. Move to node 2, calculate height of left subtree (1) and right subtree (0). Difference is $1 \le 1$.
3. Move to node 3, calculate height of left subtree (0) and right subtree (0). Difference is $0 \le 1$.

While this works, it is highly inefficient because it repeatedly calculates the height of the same lower-level nodes.

9. Naive $O(N^2)$ Implementation of Balanced Binary Tree

The naive implementation uses a helper function findHeight to calculate the depth of subtrees, calling it repeatedly for each node.

Java Implementation

public class NaiveSolution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        // Calculate heights of left and right subtrees
        int leftHeight = findHeight(root.left);
        int rightHeight = findHeight(root.right);

        // Check if current node is balanced and recursively check children
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return false;
        }

        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int findHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(findHeight(node.left), findHeight(node.right));
    }
}

Why This is Inefficient

For a skewed tree, findHeight is called on every node. The top node takes $\mathcal{O}(N)$ operations, the next takes $\mathcal{O}(N-1)$, and so on. This results in an overall time complexity of:

10. Optimized $O(N)$ Bottom-Up DFS for Balanced Binary Tree

To optimize this to $\mathcal{O}(N)$, we can combine the height calculation and balance validation into a single bottom-up traversal.

The -1 Sentinel Pattern

Instead of returning only the height, our helper function will return:

• The actual height of the subtree (a non-negative integer) if the subtree is balanced.
• -1 if any subtree is found to be unbalanced.

As we traverse up from the leaves, if we ever receive a -1 from a child subtree, we immediately propagate -1 to the parent without performing any further calculations.

Java Implementation

public class OptimizedSolution {
    public boolean isBalanced(TreeNode root) {
        // If helper returns -1, the tree is unbalanced
        return checkHeight(root) != -1;
    }

    private int checkHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 1. Check left subtree height
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) {
            return -1; // Propagate failure upwards
        }

        // 2. Check right subtree height
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) {
            return -1; // Propagate failure upwards
        }

        // 3. Check if current node is unbalanced
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // 4. Return actual height if balanced
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

11. Complete Flow Walkthrough of the Optimized Balanced Tree Algorithm

Let's trace the optimized algorithm on an unbalanced tree:

        1
       / \
      2   5
     /
    3
   /
  4

Step-by-Step Execution Trace

12. Tabular Synthesis of DFS Patterns

13. Summary and Key Takeaways

• DFS Mechanics: Recursive DFS uses the call stack to explore down to the leaf nodes before backtracking. The maximum depth of the call stack matches the height of the tree ($\mathcal{O}(H)$).
• Pointer Manipulation: Inverting a tree is a structural modification problem. Swapping pointers requires a temporary variable to prevent losing references to subtrees.
• Look-Ahead Pattern: For problems like Sum of Left Leaves, evaluating a child's properties from the parent node is often cleaner than passing parent state down to the child.
• State Reduction: The Path Sum problem is simplified by subtracting the current node's value from the target sum at each step, eliminating the need for an extra tracking variable.
• The Bottom-Up Sentinel Pattern: For validation problems involving height (like Balanced Binary Tree), returning a sentinel value (such as -1) allows you to short-circuit and propagate failures up the call stack immediately. This optimizes the time complexity from $\mathcal{O}(N^2)$ to $\mathcal{O}(N)$.