Binary Tree DFS: Recursive Framework and Paths

The Universal Framework for Binary Tree Recursion

Most Binary Tree DFS problems can be categorized into two primary templates:

Pattern 1: Backtracking (Decision-making at Pre-order Positions)

void dfs(TreeNode node, /* context data */ ...) {
    if (node == null) return;
    
    // 1. Make a choice (Enter the node, update current state)
    
    dfs(node.left, ...);
    dfs(node.right, ...);
    
    // 2. Undo the choice (Backtrack: restore state for parent context)
}

Pattern 2: Decomposition (Synthesizing Results at Post-order Positions)

int solve(TreeNode node) {
    if (node == null) return 0;         // Base Case
    
    int leftResult = solve(node.left);  // Collect result from left
    int rightResult = solve(node.right); // Collect result from right
    
    // 3. Assemble final answer using subtree results
    return f(leftResult, rightResult, node.val);
}

Path-Based Challenges

Path Sum I (LeetCode 112)

Check for a root-to-leaf path whose sum equals targetSum:

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    // Termination at a leaf node
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

Path Sum II (LeetCode 113)

Using backtracking to collect all valid root-to-leaf paths:

List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(root, targetSum, new ArrayList<>(), result);
    return result;
}

void backtrack(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
    if (node == null) return;
    
    // Step 1: Add node to path
    path.add(node.val);
    remain -= node.val;
    
    // Step 2: Goal condition (leaf node with zero remainder)
    if (node.left == null && node.right == null && remain == 0) {
        res.add(new ArrayList<>(path)); // Store a snapshot
    }
    
    dfs(node.left, remain, path, res);
    dfs(node.right, remain, path, res);
    
    // Step 3: Backtrack (remove node from current stack frame)
    path.remove(path.size() - 1);
}

Binary Tree Maximum Path Sum (LeetCode 124)

Find the maximum path sum between any two nodes.
Insight: While a path can span both subtrees at a specific "peak" node, the value reported back to the parent can only extend down one side (left or right).

int maxGlobalSum = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    calculateContribution(root);
    return maxGlobalSum;
}

int calculateContribution(TreeNode node) {
    if (node == null) return 0;
    
    // Ignore negative contributions
    int left = Math.max(0, calculateContribution(node.left));
    int right = Math.max(0, calculateContribution(node.right));
    
    // Update global maximum considering the current node as the "highest" point (peak)
    maxGlobalSum = Math.max(maxGlobalSum, left + right + node.val);
    
    // Only return the max of one side to the caller (parent)
    return node.val + Math.max(left, right);
}

Structural Property Challenges

Balanced Binary Tree (LeetCode 110)

Post-order traversal: subtrees calculate heights first and detect imbalance.

boolean isBalanced(TreeNode root) {
    return getHeight(root) != -1;
}

int getHeight(TreeNode node) {
    if (node == null) return 0;
    
    int lh = getHeight(node.left);
    int rh = getHeight(node.right);
    
    // If any subtree is unbalanced, bubble up the failure
    if (lh == -1 || rh == -1) return -1;
    if (Math.abs(lh - rh) > 1) return -1;
    
    return 1 + Math.max(lh, rh);
}

Diameter of Binary Tree (LeetCode 543)

int maxDiameter = 0;

int diameterOfBinaryTree(TreeNode root) {
    calculateDepth(root);
    return maxDiameter;
}

int calculateDepth(TreeNode node) {
    if (node == null) return 0;
    int leftDepth = calculateDepth(node.left);
    int rightDepth = calculateDepth(node.right);
    
    // Update diameter at every node
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    
    return 1 + Math.max(leftDepth, rightDepth);
}

Lowest Common Ancestor (LeetCode 236)

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 p and q split between subtrees, current node is the LCA
    if (left != null && right != null) return root;
    
    // Otherwise, bubble up the found signal
    return left != null ? left : right;
}

Path vs. Property Comparison