135. Path Sum
🔗 LeetCode Problem: 112. Path Sum
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, Recursion, DFS, Path Problems, Leaf Nodes
Problem Statement
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: No root-to-leaf path has sum = 5
Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Empty tree has no paths
Constraints:
- The number of nodes in the tree is in the range [0, 5000]
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
🌳 Visual Understanding - Drawing the Problem!
Example 1: Path Exists ✓
Tree: [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22
Visual Tree:
5 Sum so far: 5
/ \
4 8 4: 5+4=9, 8: 5+8=13
/ / \
11 13 4 11: 9+11=20, 13: 13+13=26, 4: 13+4=17
/ \ /
7 2 1 7: 20+7=27, 2: 20+2=22 ✓, 1: 17+1=18
Paths to leaves:
Path 1: 5 → 4 → 11 → 7 = 5+4+11+7 = 27 ✗
Path 2: 5 → 4 → 11 → 2 = 5+4+11+2 = 22 ✓ FOUND!
Path 3: 5 → 8 → 13 = 5+8+13 = 26 ✗
Path 4: 5 → 8 → 4 → 1 = 5+8+4+1 = 18 ✗
Result: true (Path 2 equals target)
Example 2: No Valid Path ✗
Tree: [1,2,3]
targetSum = 5
Visual Tree:
1 Sum: 1
/ \
2 3 2: 1+2=3, 3: 1+3=4
Paths to leaves:
Path 1: 1 → 2 = 1+2 = 3 ✗
Path 2: 1 → 3 = 1+3 = 4 ✗
No path equals 5
Result: false
⚠️ THE CRITICAL GOTCHA - Must Reach a LEAF!
This is similar to Minimum Depth gotcha!
Tree:
5
/
4
/
11
/
7
targetSum = 5
WRONG THINKING:
"Node 5 equals targetSum 5, return true!" ✗
CORRECT THINKING:
"Node 5 is NOT a leaf (has child 4)
Must continue to a leaf!
Path 5→4→11→7 = 27 ≠ 5
Return false" ✓
KEY RULE: Path must reach a LEAF node!
Understanding "Root-to-Leaf" Path:
Valid Path:
5
/ \
4 8 ← Both 4 and 8 have children
/
11 ← Has children
/
7 ← LEAF! ✓ This is a valid endpoint
Invalid "Path":
5 ← Not a leaf
/
4 ← Not a leaf, can't stop here
A path MUST end at a leaf (node with no children)!
🧠 The AHA Moment - Recursive Insight!
The Key Question:
"Does a path from current node to a leaf equal targetSum?"
Recursive Breakdown:
Think of it as reducing the problem:
At node with value V, target T:
"Is there a path from HERE to a leaf that sums to T?"
This becomes:
"Is there a path from my LEFT child to a leaf that sums to (T - V)?"
OR
"Is there a path from my RIGHT child to a leaf that sums to (T - V)?"
Why T - V?
We've already "used up" V from the target!
Children need to make up the REMAINING sum!
Visual Example:
5 targetSum = 22
/
4 At 5: Does path to leaf = 22?
/ → Check if children have path = 22 - 5 = 17
11
/
2
At node 5:
"I contribute 5 to the sum"
"My children need to contribute 22 - 5 = 17"
"Does my left child (4) have a path summing to 17?"
At node 4:
"I contribute 4 to the sum"
"My parent already used 5, so I need 17 remaining"
"My children need to contribute 17 - 4 = 13"
"Does my left child (11) have a path summing to 13?"
At node 11:
"I contribute 11 to the sum"
"Ancestors used 5+4=9, I need 13 remaining"
"My children need to contribute 13 - 11 = 2"
"Does my left child (2) have a path summing to 2?"
At node 2:
"I contribute 2 to the sum"
"I need 2 remaining"
"I'm a LEAF and my value is 2"
"2 == 2? YES! ✓"
"Return true!"
🧠 Recursive Thinking - Building the Solution
Base Cases:
Base Case 1: Node is null
return false
WHY? No node means no path
Can't have a sum from nothing!
Base Case 2: Node is a LEAF
return (node.val == targetSum)
WHY? We've reached the end of a path
Check if this leaf completes the target sum!
CRITICAL: This is our SUCCESS check!
We can only return true at a LEAF!
Recursive Case:
For any non-leaf node:
1. Subtract current node's value from target
remaining = targetSum - node.val
2. Check if either subtree has a path with remaining sum
leftHasPath = hasPathSum(node.left, remaining)
rightHasPath = hasPathSum(node.right, remaining)
3. Return true if either path exists
return leftHasPath || rightHasPath
Why OR?
We only need ONE path to equal the target
If either left OR right has a valid path, we're good!
The Complete Logic:
hasPathSum(node, targetSum):
if node is null:
return false
if node is LEAF:
return node.val == targetSum
// Not a leaf, check children
remaining = targetSum - node.val
leftPath = hasPathSum(node.left, remaining)
rightPath = hasPathSum(node.right, remaining)
return leftPath || rightPath
🎯 Solution: Recursive DFS
Implementation:
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
// Base Case 1: Empty tree has no paths
if (root == null) {
return false;
}
// Base Case 2: Leaf node - check if it completes the path
// WHY? Path must end at a leaf!
// This is our ONLY success condition!
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
// Recursive Case: Check if either subtree has path
// with remaining sum (targetSum - current node value)
// WHY? We've "used up" current node's value
int remaining = targetSum - root.val;
boolean leftPath = hasPathSum(root.left, remaining);
boolean rightPath = hasPathSum(root.right, remaining);
// Return true if either subtree has a valid path
// WHY? We only need ONE path to satisfy the condition
return leftPath || rightPath;
}
}
Cleaner Version:
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
// Null check
if (root == null) {
return false;
}
// Leaf check - only place we can return true!
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
// Check both subtrees with remaining sum
int remaining = targetSum - root.val;
return hasPathSum(root.left, remaining) ||
hasPathSum(root.right, remaining);
}
}
Ultra-Concise Version:
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
}
🔍 Detailed Dry Run with Recursion Visualization
Tree:
5
/
4
/
11
/
2
targetSum = 22
Complete Recursion Flow:
CALL STACK VISUALIZATION:
Level 0: hasPathSum(5, 22)
│
├─ root = 5, not null ✓
├─ root is not a leaf (has left child)
├─ remaining = 22 - 5 = 17
│
├─ Check LEFT: hasPathSum(4, 17) ──────────┐
│ │
│ Level 1: hasPathSum(4, 17) │
│ │ │
│ ├─ root = 4, not null ✓ │
│ ├─ root is not a leaf (has left child) │
│ ├─ remaining = 17 - 4 = 13 │
│ │ │
│ ├─ Check LEFT: hasPathSum(11, 13) ─────┐
│ │ │
│ │ Level 2: hasPathSum(11, 13) │
│ │ │ │
│ │ ├─ root = 11, not null ✓ │
│ │ ├─ root is not a leaf (has child) │
│ │ ├─ remaining = 13 - 11 = 2 │
│ │ │ │
│ │ ├─ Check LEFT: hasPathSum(2, 2) ───┐
│ │ │ │
│ │ │ Level 3: hasPathSum(2, 2) │
│ │ │ │ │
│ │ │ ├─ root = 2, not null ✓ │
│ │ │ ├─ root IS A LEAF! ✓ │
│ │ │ ├─ Check: 2 == 2? YES! ✓ │
│ │ │ └─ return true ✓ │
│ │ │ │
│ │ ├─ leftPath = true ✓ │
│ │ ├─ No need to check right (OR) │
│ │ └─ return true ✓ │
│ │ │
│ ├─ leftPath = true ✓ │
│ ├─ No need to check right (OR) │
│ └─ return true ✓ │
│ │
├─ leftPath = true ✓ │
├─ No need to check right (OR short-circuit)
└─ return true ✓ │
FINAL RESULT: true ✓
Path found: 5 → 4 → 11 → 2 = 22 ✓
What Each Node "Sees":
Node 5 asks:
"Do I have a path to a leaf summing to 22?"
"I'm worth 5, so my children need to sum to 17"
"Left child (4), do you have a path summing to 17?"
→ Gets back: true ✓
"Great! I found a path!"
→ Returns: true ✓
Node 4 asks:
"Do I have a path to a leaf summing to 17?"
"I'm worth 4, so my children need to sum to 13"
"Left child (11), do you have a path summing to 13?"
→ Gets back: true ✓
"Perfect! I found a path!"
→ Returns: true ✓
Node 11 asks:
"Do I have a path to a leaf summing to 13?"
"I'm worth 11, so my children need to sum to 2"
"Left child (2), do you have a path summing to 2?"
→ Gets back: true ✓
"Excellent! I found a path!"
→ Returns: true ✓
Node 2 (LEAF) says:
"I'm a leaf and I need to equal 2"
"My value is 2"
"2 == 2? YES! ✓"
→ Returns: true ✓
🔍 Dry Run - Example with NO Valid Path
Tree:
1
/ \
2 3
targetSum = 5
Recursion Flow:
Level 0: hasPathSum(1, 5)
│
├─ root = 1, not null ✓
├─ root is not a leaf (has children)
├─ remaining = 5 - 1 = 4
│
├─ Check LEFT: hasPathSum(2, 4) ──────────┐
│ │
│ Level 1: hasPathSum(2, 4) │
│ │ │
│ ├─ root = 2, not null ✓ │
│ ├─ root IS A LEAF! ✓ │
│ ├─ Check: 2 == 4? NO! ✗ │
│ └─ return false ✗ │
│ │
├─ leftPath = false ✗ │
│ │
├─ Check RIGHT: hasPathSum(3, 4) ─────────┐
│ │
│ Level 1: hasPathSum(3, 4) │
│ │ │
│ ├─ root = 3, not null ✓ │
│ ├─ root IS A LEAF! ✓ │
│ ├─ Check: 3 == 4? NO! ✗ │
│ └─ return false ✗ │
│ │
├─ rightPath = false ✗ │
│ │
└─ return false || false = false ✗ │
FINAL RESULT: false ✗
No path sums to 5:
Path 1: 1 → 2 = 3 ✗
Path 2: 1 → 3 = 4 ✗
🔍 The Gotcha - Example That Catches People
Tree:
5
targetSum = 5
Common WRONG Approach:
❌ WRONG THINKING:
hasPathSum(5, 5):
"Root value is 5"
"Target is 5"
"5 == 5, so return true!" ✗
WHY WRONG?
Node 5 is NOT a leaf!
It's the root but has no children
Wait... it HAS no children!
So it IS a leaf!
This one is actually CORRECT! ✓
The REAL Gotcha:
Tree:
5
/
4
targetSum = 5
❌ WRONG APPROACH:
"Root value is 5"
"Target is 5"
"5 == 5, return true!" ✗
WHY WRONG?
Node 5 is NOT a leaf (has child 4)!
Path must continue to a leaf!
Only path: 5 → 4 = 9 ≠ 5
✓ CORRECT APPROACH:
hasPathSum(5, 5):
root = 5, not null ✓
root.left = 4 (not null), so NOT a leaf
remaining = 5 - 5 = 0
Check left: hasPathSum(4, 0)
root = 4, IS a leaf ✓
Check: 4 == 0? NO! ✗
return false ✗
Check right: null
return false ✗
return false || false = false ✓
Result: false ✓
📊 Complexity Analysis
Time Complexity: O(n)
Where n = number of nodes in the tree
Why?
- We visit each node at most once
- At each node, we do O(1) work
- Even with OR short-circuiting, worst case visits all nodes
Best case (path found early):
- Might not visit all nodes
- Still O(n) worst case
Example:
1
/ \
2 3
/ \
4 5
If path exists at node 4, we visit: 1, 2, 4 (3 nodes)
If no path exists, we visit all 5 nodes
Space Complexity: O(h)
Where h = height of the tree
Why?
- Recursion call stack depth
- Maximum depth = height of tree
Best case (balanced tree): O(log n)
Example: Perfect binary tree with 15 nodes
Height = 4 → Stack depth = 4
Worst case (skewed tree): O(n)
Example:
1
/
2
/
3
Height = 3 → Stack depth = 3
For n nodes in skewed tree: h = n
⚠️ Common Mistakes - The Gotchas!
Mistake 1: Not Checking for Leaf
// ❌ WRONG - Can return true at non-leaf nodes!
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.val == targetSum) return true; // WRONG!
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
// Tree: 5
// /
// 4
// targetSum = 5
// This returns TRUE at node 5 (non-leaf)
// Should return FALSE (only path is 5→4=9)
// ✓ CORRECT - Check if it's a leaf!
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// Must be a LEAF to return true!
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
Mistake 2: Wrong Leaf Definition
// ❌ WRONG - Thinks one null child means leaf
if (root.left == null || root.right == null) {
return root.val == targetSum; // WRONG!
}
// Tree: 5
// /
// 4
// At node 5: right is null, but left exists!
// This would treat 5 as a leaf (WRONG!)
// ✓ CORRECT - Both children must be null
if (root.left == null && root.right == null) {
return root.val == targetSum; // Correct!
}
Mistake 3: Not Subtracting Current Value
// ❌ WRONG - Passes same targetSum to children
return hasPathSum(root.left, targetSum) ||
hasPathSum(root.right, targetSum);
// This doesn't account for current node's contribution!
// Children should get REMAINING sum, not full target!
// ✓ CORRECT - Subtract current value
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
Mistake 4: Checking Sum at Every Node
// ❌ WRONG - Accumulating sum instead of reducing target
public boolean hasPathSum(TreeNode root, int targetSum, int currentSum) {
if (root == null) return false;
currentSum += root.val;
if (currentSum == targetSum) return true; // Wrong approach!
// ...
}
// This complicates the logic and can return true at non-leaves
// ✓ CORRECT - Reduce target, check only at leaves
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
Mistake 5: Forgetting OR Logic
// ❌ WRONG - Uses AND instead of OR
return hasPathSum(root.left, remaining) &&
hasPathSum(root.right, remaining);
// This requires BOTH paths to work!
// We only need ONE valid path!
// ✓ CORRECT - Use OR
return hasPathSum(root.left, remaining) ||
hasPathSum(root.right, remaining);
Mistake 6: Empty Tree Edge Case
// ❌ WRONG - Doesn't handle null input
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root.left == null && root.right == null) {
return root.val == targetSum; // NullPointerException if root is null!
}
// ...
}
// ✓ CORRECT - Check null first!
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false; // Handle null first!
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
// ...
}
🎯 Pattern Recognition - Path Problems
Core Pattern: Root-to-Leaf Paths
Template for root-to-leaf path problems:
boolean/int pathProperty(TreeNode node, int target) {
// Base: null
if (node == null) return false/defaultValue;
// Base: LEAF - this is where we check condition!
if (node.left == null && node.right == null) {
return checkCondition(node.val, target);
}
// Recursive: Update target and check children
int newTarget = updateTarget(target, node.val);
// Use OR for "exists" problems, other logic for calculations
return pathProperty(node.left, newTarget) ||
pathProperty(node.right, newTarget);
}
Related Problems:
1. Path Sum II (Return All Paths)
Instead of returning boolean:
- Collect all paths that sum to target
- Use backtracking
- Return List<List<Integer>>
Similar pattern:
- Still must reach leaf
- Still reduce target
- But track the path
2. Path Sum III (Any Path, Not Just Root-to-Leaf)
Different problem:
- Path can start anywhere
- Path can end anywhere
- Doesn't need to reach leaf!
Pattern changes significantly
3. Binary Tree Maximum Path Sum
Find path with maximum sum
- Path can start/end anywhere
- More complex than this problem
- Uses depth as helper
4. Sum Root to Leaf Numbers
Each path forms a number
Example: 1→2→3 forms "123"
Similar pattern:
- Must reach leaf
- But construct number instead of sum
5. Minimum Depth (Problem 134)
Same leaf requirement!
- Path must reach leaf
- Can't stop at non-leaf node
This is why we learned it before!
When to Use This Pattern:
✓ "Root-to-leaf path" mentioned
✓ Must reach a leaf node
✓ Path sum calculations
✓ Path validation problems
✓ Any problem requiring "complete path"
📝 Quick Revision Notes
🎯 Core Concept
Find if any root-to-leaf path sums to target. Key: must reach a LEAF (both children null). At each node, subtract current value from target. Check children with remaining sum. Return true if any leaf equals remaining target. Use OR logic (only need one valid path).
⚡ Quick Implementation
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
}
class Solution {
public boolean hasPathSum(TreeNode root, int k) {
// base case when tree itself is empty, need to return false per question.
// Due to this base case only, we separated out util method.
if(root == null) {
return false;
}
return hasPathSumUtil(root, k);
}
private boolean hasPathSumUtil(TreeNode root, int k) {
// Reached leaf node. This node value should be equal to k.
// path sum means sum should become 0 at leaf node only (**)
if(root.left == null && root.right == null) {
return root.val == k;
}
int newK = k - root.val;
// Why we are branching like this?
// It is asked leaf node.
// Consider [1,2,null] and k = 1, where 1 is parent and (2, null) are its left and right child.
// In this case, hasPathSumUtil(1.right, 0) would give true. But, we need to consider full path
// from root node to leaf node. Hence, we should branch out like below.
if(root.left == null) {
return hasPathSumUtil(root.right, newK);
}
if(root.right == null) {
return hasPathSumUtil(root.left, newK);
}
// post reducing the current node value (k - root.val), check if any
// paths (left or right) would contribute to the result.
return hasPathSumUtil(root.left, newK) || hasPathSumUtil(root.right, newK);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.hasPathSum(TreeNode.buildTree(new Integer[] {5,4,8,11,null,13,4,7,2,null,null,null,1}), 22));
System.out.println(s.hasPathSum(TreeNode.buildTree(new Integer[] {1,2,3}), 5));
System.out.println(s.hasPathSum(TreeNode.buildTree(new Integer[] {1,2}), 1));
}
}
🔑 Key Insights
The Leaf Requirement:
Tree: 5 targetSum = 5
/
4
❌ WRONG: "5 == 5, return true"
✓ CORRECT: "5 is not a leaf, must continue"
Only leaves can satisfy the condition!
Reducing the Target:
At each node:
"I contribute my value"
"My children need to make up the REST"
remaining = targetSum - current.val
This simplifies the recursion!
Instead of tracking accumulated sum,
we reduce what's needed!
OR vs AND Logic:
Use OR (||):
"Does LEFT have a path OR does RIGHT have a path?"
Only need ONE valid path to return true!
Don't use AND (&&):
That would require BOTH paths to work!
🎪 Memory Aid
"Leaf or nothing - can't stop halfway!"
"Take my value, pass the rest down!"
"Either path works - use OR!"
"Success only at leaves!" ✨
⚠️ Don't Forget
- Check null FIRST (before accessing properties)
- Leaf = both children null (not just one!)
- Success ONLY at leaves (can't return true elsewhere!)
- Subtract current value (pass remaining to children)
- Use OR logic (||, not &&)
- Empty tree returns false (no paths possible)
🔗 Decision Tree
Is node null?
→ return false
Is node a leaf (both children null)?
→ return node.val == targetSum
Node has children:
→ remaining = targetSum - node.val
→ return hasPathSum(left, remaining) ||
hasPathSum(right, remaining)
🎉 Congratulations!
You've mastered root-to-leaf path problems!
What You Learned:
✅ Leaf requirement - Path must reach a leaf
✅ Reducing target - Subtract instead of accumulate
✅ OR logic - Only need one valid path
✅ Base cases - Null and leaf handling
✅ Common gotcha - Non-leaf nodes can't satisfy condition
✅ Pattern template - Applies to many path problems
Connection to Previous Problems:
Problem 133 (Max Depth):
Return: int (calculation)
Any path: yes
Problem 134 (Min Depth):
Return: int (calculation)
Must reach leaf: YES! ✓ (same requirement!)
Problem 135 (Path Sum):
Return: boolean (validation)
Must reach leaf: YES! ✓ (same requirement!)
Pattern: Leaf requirement appears in multiple problems!
The Core Pattern You Learned:
// Root-to-leaf pattern
boolean check(TreeNode node, int target) {
if (node == null) return false;
// CRITICAL: Check at leaf only!
if (isLeaf(node)) {
return node.val == target;
}
// Reduce target, check children
int remaining = target - node.val;
return check(node.left, remaining) ||
check(node.right, remaining);
}
This pattern appears in MANY problems!
Next Steps:
Perfect problems to practice: - Path Sum II (collect all valid paths) - Sum Root to Leaf Numbers (construct numbers from paths) - Binary Tree Paths (find all root-to-leaf paths)
You're building strong path problem skills! 🌳🎯✨