Path Sum LeetCode 112 — DFS Guide

LeetCode 112 — Path Sum — gives you the root of a binary tree and an integer targetSum. You must return true if there exists a root-to-leaf path such that the sum of all node values along the path equals targetSum. A path must start at the root and end at a leaf node — a node with no children.

The definition of a leaf is crucial here: a leaf is a node with no left child and no right child. An internal node — even one whose value equals targetSum — does not count as the end of a valid path. This distinction drives how you write the base case in any recursive solution.

Edge cases: an empty tree (root is null) always returns false, even if targetSum is 0. A tree with a single node returns true only if that node's value equals targetSum. These boundary conditions are easy to handle in the recursive implementation because the base cases cover them naturally.

The most elegant approach is DFS with subtraction rather than accumulation. Instead of carrying a running sum and comparing it to targetSum at a leaf, you subtract each node's value from the target as you descend. When you reach a leaf, you simply check whether the remaining value equals zero.

This subtraction strategy eliminates the need for an extra parameter to track the accumulated sum. The target itself becomes the running state — at each recursive call you pass targetSum minus the current node's value. The recursive signature stays the same as the original function: hasPathSum(node, targetSum).

The subtraction approach also makes the base cases extremely clear. If the node is null, return false — no path can be completed through a null. If the node is a leaf (no children), return whether targetSum minus node.val equals zero, which is the same as checking if node.val equals the remaining target. For internal nodes, recurse on the left and right children with the updated target.

The recursive implementation is four lines in Python: if not root, return False; if not root.left and not root.right, return targetSum == root.val; return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val). Each line maps directly to one of the three cases: null node, leaf node, or internal node.

The OR in the internal node case is key: you only need one valid path, so you short-circuit as soon as one subtree returns true. If the left subtree finds a valid path, the right subtree is never explored. This makes the best-case performance O(log n) for a balanced BST where the answer is found in the first leaf reached.

The time complexity is O(n) in the worst case — you may need to visit every node when no valid path exists. The space complexity is O(h) for the call stack where h is the tree height, giving O(log n) for a balanced tree and O(n) for a degenerate (linked-list-like) tree.

The requirement that the path ends at a leaf is the most common source of bugs in this problem. A naive implementation might check if the current node's value equals the remaining target without verifying that the node has no children. This produces incorrect results on trees where an internal node happens to equal the remaining target.

Consider a tree [5, null, 8] with targetSum = 5. The root has value 5 and a right child 8. The correct answer is false because node 5 is not a leaf — it has a right child. A buggy solution that checks node.val == remaining at any node would return true here, incorrectly treating the root as a valid path endpoint.

The fix is always to check both conditions together at the leaf base case: the node must have no children AND targetSum - node.val must equal zero. Checking only one condition is always wrong. This two-condition check is the critical invariant that makes the algorithm correct.

The iterative version uses an explicit stack of (node, remaining) pairs instead of the call stack. Initialize the stack with [(root, targetSum)]. On each iteration, pop a pair, check if the node is a leaf with remaining == 0 (return true if so), then push the left child with remaining - node.val and the right child with remaining - node.val if they exist.

The iterative approach avoids stack overflow on deep trees. For a degenerate binary tree (every node has only one child), the recursive version uses O(n) stack frames which can cause a RecursionError in Python for very large inputs. The iterative version uses a heap-allocated list that grows to O(n) in the worst case but never overflows the call stack.

Both approaches are O(n) time and O(n) space in the worst case. The iterative version is slightly more verbose but preferred when the tree could be very deep. In interview settings, presenting both and explaining the trade-off demonstrates strong understanding of the recursive-to-iterative translation.

Python recursive (4 lines): def hasPathSum(root, targetSum): if not root: return False; if not root.left and not root.right: return targetSum == root.val; return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val). O(n) time O(h) space. Python iterative with stack: def hasPathSum(root, targetSum): stack = [(root, targetSum)]; while stack: node, rem = stack.pop(); if not node.left and not node.right and rem == node.val: return True; if node.left: stack.append((node.left, rem - node.val)); if node.right: stack.append((node.right, rem - node.val)); return False.

Java recursive: public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null) return targetSum == root.val; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); }. Four lines, clean and interview-standard. The || short-circuits on the first true result, so you never explore both subtrees unnecessarily.

Both versions are O(n) time and O(h) space where h is the tree height. For a balanced binary tree h = O(log n). For a degenerate tree h = O(n). The recursive version is preferred for clarity in interviews. The iterative version is preferred when the tree depth could overflow the call stack. Understanding both and the trade-offs is essential interview preparation.

Path Sum II (LeetCode 113) extends this problem by asking for all root-to-leaf paths that sum to the target, not just whether one exists. It uses DFS with backtracking: carry the current path as a list, add the current node at entry, and pop it at exit. When a valid leaf is found, append a copy of the current path to the results list. Time O(n^2) because copying each valid path takes O(n).

Path Sum III (LeetCode 437) is the hardest variant: find the number of paths that sum to the target where the path can start and end at any node (not just root-to-leaf). It uses prefix sum with a hash map: track the running sum from root to each node, and count how many previous prefix sums equal currentSum - target. This gives O(n) time using the same trick as subarray sum equals k (LeetCode 560).

Binary Tree Maximum Path Sum (LeetCode 124) is a different direction: find the path (any node to any node, not necessarily root-to-leaf) with the maximum sum. It requires postorder DFS where each node returns its best single-branch gain to its parent, while updating a global maximum that includes both branches. The path sum family — 112, 113, 437, 124 — covers the major DFS techniques for tree paths.