Tree DFS (Depth-First Search)

🌳 Tree DFS - Path Sum (Target: 23)

Current Path:

Sum: 12

Step 1: Start at root (12), sum = 12

Progress: 1 / 11

Speed:

Legend:

Current Node

In Current Path

Path Found!

🎯 Explain Like I'm 5...

Imagine exploring a big tree house with many rooms! DFS means you go ALL THE WAY DOWN one hallway before trying another!

🚪 Two Ways to Explore (BFS vs DFS):

BFS: BFS (Floor by Floor): Visit ALL rooms on floor 1, then ALL on floor 2, then ALL on floor 3

DFS: DFS (Deep Dive): Go to room 1, then go ALL THE WAY down its hallway to the deepest room. Then come back and try the next hallway!

• Start at Grandpa's room 👴
• Go to Dad's room (down the left hallway) 👨
• Keep going down to Kid's room (deepest room!) 👦
• Come back, try the RIGHT hallway
• Go to Mom's room, then down to her kid's rooms...

🚀 The Secret: DFS is like leaving breadcrumbs! Go deep, and when you hit a dead end, follow your breadcrumbs back and try another path. Perfect for finding paths or counting things! 🍞

When Should You Use This Pattern?

✓Finding paths from root to leaf
✓Problems involving tree depth or height
✓Checking if a path exists with a certain property
✓When you need to visit all nodes and use less memory than BFS

📝 Example 1: Binary Tree Path Sum

Given a binary tree and a number, find if there exists a root-to-leaf path with sum equal to the number.

Step-by-Step Thinking:

Start at root, subtract root value from target sum
Recursively check left and right subtrees
At leaf node, check if remaining sum equals leaf value
If any path works, return true!

PathSum.java

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
public class PathSum {
    // Check if there's a root-to-leaf path with given sum
    public static boolean hasPathSum(TreeNode root, int sum) {
        // Base case: empty tree
        if (root == null) {
            return false;
        }
        // Check if we're at a leaf node
        if (root.left == null && root.right == null) {
            return root.val == sum;  // Does leaf value match remaining sum?
        }
        // Recursively check left and right subtrees
        // Subtract current node's value from sum
        return hasPathSum(root.left, sum - root.val)
            || hasPathSum(root.right, sum - root.val);
    }
    public static void main(String[] args) {
        // Tree:      12
        //           /  \
        //          7    1
        //         / \    \
        //        4   10   5
        TreeNode root = new TreeNode(12);
        root.left = new TreeNode(7);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(10);
        root.right.right = new TreeNode(5);
        System.out.println("Path with sum 23: " + hasPathSum(root, 23));
        // Output: true (12 + 7 + 4 = 23)
        System.out.println("Path with sum 16: " + hasPathSum(root, 16));
        // Output: false
    }
}

📝 Example 2: All Root-to-Leaf Paths

Find all root-to-leaf paths in a binary tree.

AllPaths.java

java

import java.util.*;
public class AllPaths {
    public static List<List<Integer>> findPaths(TreeNode root) {
        List<List<Integer>> allPaths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        findPathsRecursive(root, currentPath, allPaths);
        return allPaths;
    }
    private static void findPathsRecursive(TreeNode node,
                                           List<Integer> currentPath,
                                           List<List<Integer>> allPaths) {
        if (node == null) {
            return;
        }
        // Add current node to path
        currentPath.add(node.val);
        // If it's a leaf, save the current path
        if (node.left == null && node.right == null) {
            allPaths.add(new ArrayList<>(currentPath));
        } else {
            // Explore left and right subtrees
            findPathsRecursive(node.left, currentPath, allPaths);
            findPathsRecursive(node.right, currentPath, allPaths);
        }
        // Backtrack: remove current node before returning
        currentPath.remove(currentPath.size() - 1);
    }
    public static void main(String[] args) {
        // Tree:      1
        //           / \
        //          2   3
        //         / \
        //        4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        List<List<Integer>> paths = findPaths(root);
        System.out.println("All paths:");
        for (List<Integer> path : paths) {
            System.out.println(path);
        }
        // Output:
        // [1, 2, 4]
        // [1, 2, 5]
        // [1, 3]
    }
}

📝 Example 3: Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree.

MaxDepth.java

java

public class MaxDepth {
    // Find maximum depth of tree
    public static int maxDepth(TreeNode root) {
        // Base case: empty tree has depth 0
        if (root == null) {
            return 0;
        }
        // Recursively find depth of left and right subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        // Maximum depth is the larger of the two, plus 1 for current node
        return Math.max(leftDepth, rightDepth) + 1;
    }
    // Alternative: Check if tree is balanced
    public static boolean isBalanced(TreeNode root) {
        return checkHeight(root) != -1;
    }
    private static int checkHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = checkHeight(node.left);
        if (leftHeight == -1) return -1;  // Left subtree unbalanced
        int rightHeight = checkHeight(node.right);
        if (rightHeight == -1) return -1;  // Right subtree unbalanced
        // Check if current node is balanced
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;  // Unbalanced
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
    public static void main(String[] args) {
        // Tree:      1
        //           / \
        //          2   3
        //         / \
        //        4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.println("Maximum depth: " + maxDepth(root));
        // Output: 3
        System.out.println("Is balanced: " + isBalanced(root));
        // Output: true
    }
}

🔑 Key Points to Remember

1️⃣DFS uses recursion (or explicit stack) vs BFS uses queue
2️⃣Three types: Preorder (root first), Inorder (left-root-right), Postorder (children first)
3️⃣Time Complexity: O(n) - visit each node once
4️⃣Space Complexity: O(h) where h is height (recursion stack)

💪 Practice Problems

• Sum of Path Numbers
• Path With Given Sequence
• Count Paths for a Sum
• Diameter of Binary Tree
• Lowest Common Ancestor