Path Sum
Mahabharata — The Targeted Journey — Does Any Root-to-Leaf Path Sum to the Target?
पत्ती तक — लक्ष्य योग। हर नोड पर — घटाओ, आगे बढ़ो; पत्ती पर — शेष जाँचो॥
*To the leaf — target sum. At each node — subtract, advance; at leaf — check what remains.*
The Story
Does there exist a root-to-leaf path where the sum of node values equals `targetSum`?
For tree `[5,4,8,11,null,13,4,7,2,null,null,null,1]`, targetSum=22: true (5→4→11→2=22).
**Recursive approach:** - At each node: subtract its value from targetSum - At a leaf: check if remaining targetSum == 0 - Recurse left and right
```java public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null) // Leaf return targetSum == root.val; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } ```
Trace `[5,4,11,7,2]`, targetSum=22: - hasPathSum(5, 22): not leaf. Try left with 22-5=17, right with 17. - hasPathSum(4, 17): not leaf. Try left with 17-4=13. - hasPathSum(11, 13): not leaf. Try left(13-11=2), right(13-11=2). - hasPathSum(7, 2): leaf. 2==7? No. - hasPathSum(2, 2): leaf. 2==2? Yes! → return true ✓
**Important:** The leaf check (`left == null && right == null`) is crucial. Without it, null nodes would falsely return true when targetSum becomes 0 at a non-leaf path.
The DFS with Path Collection
DFS collecting current path sum. At leaf: check if sum equals target. O(n).
boolean hasPathSumDFS(TreeNode root, int target, int current) {
if (root == null) return false;
current += root.val;
if (root.left == null && root.right == null) return current == target;
return hasPathSumDFS(root.left, target, current)
|| hasPathSumDFS(root.right, target, current);
}The Subtract-and-Check-at-Leaf Wisdom
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);
}Step-by-Step Walkthrough
Single node [1], target=1: leaf check: 1==1 → true ✅ Single node [1], target=2: leaf check: 2==1 → false ✅ Null tree, target=0: return false (null → false, NOT true) ✅
Deep Insight
**The leaf check vs null check:** Why check leaf instead of null? - If we returned true when `root==null && targetSum==0`, then path `[5,null]` with target=5 would return true at root=5's null child — but that's not a root-to-leaf path! - The leaf check ensures we only accept paths that actually end at a leaf node.
**Short-circuit with `||`:** Java's `||` short-circuits — if left subtree returns true, right is not explored. This is the O(h) best case for early success.
**Foundation for tr-27, tr-28, tr-29:** Path Sum is the base pattern for all path-related tree problems.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(h) | DFS with current sum parameter |
| Optimal | O(n) | O(h) | Same complexity — recursive is already optimal |
Pattern Recognition
✅ Path sum: subtract root.val at each node ✅ Leaf check: left==null && right==null ✅ Return true at leaf if remaining==0 ✅ Foundation for Path Sum II, III **LeetCode Trigger Phrases:** → "path sum" — root to leaf → Does any root-to-leaf path equal target → DFS subtracting target as you descend
Bhagavad Gita 9.22
अनन्याश्चिन्तयन्तो मां ये जनाः पर्युपासते। तेषां नित्याभियुक्तानां योगक्षेमं वहाम्यहम्॥
Those who worship Me with devotion, meditating on My transcendental form — to them who are constantly engaged, I carry what they lack and preserve what they have.
Connection: The path sum algorithm searches for the one path — the devoted path from root to leaf — that reaches exactly the target. Like the devotee who follows one path with complete focus, the algorithm explores each root-to-leaf path with single-minded purpose: does this path's total equal the target? Each node carries the remaining target downward, and at the leaf (the journey's end), the devotion is validated — or the search continues on a different path.