#112 Path Sum
the problem
In plain words
Given a binary tree and a number targetSum, return true if some path from the root down to a leaf has values adding up to exactly targetSum. A leaf is a node with no children. An empty tree has no paths.
in root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
out true
5 + 4 + 11 + 2 = 22.
in root = [1,2,3], targetSum = 5
out false
The two root-to-leaf sums are 3 and 4.
in root = [], targetSum = 0
out false
No nodes, no paths.
- 0 ≤ number of nodes ≤ 5000
- -1000 ≤ Node.val ≤ 1000
- -1000 ≤ targetSum ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (top-down)
Pass the remaining target down: each node subtracts its value and asks its children for the rest. Only a leaf may say "done" — when exactly 0 is left.
solutions
From brute force to optimal
Collect every root-to-leaf path as its own list, then sum each list and compare with the target.
- DFS with a path list; at every leaf, store a copy.
- For each stored path, add up its values.
- Return true if any sum equals targetSum.
Each leaf copies and re-adds a path of up to h values — O(n²) on a broom-shaped tree (a long handle with many leaves).
All the stored paths at once.
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { List<List<Integer>> paths = new ArrayList<>(); collect(root, new ArrayList<>(), paths); for (List<Integer> path : paths) { // add up every stored path from scratch int sum = 0; for (int v : path) sum += v; if (sum == targetSum) return true; } return false; } /** Stores every root-to-leaf path as its own list. */ private void collect(TreeNode node, List<Integer> path, List<List<Integer>> paths) { if (node == null) return; path.add(node.val); if (node.left == null && node.right == null) paths.add(new ArrayList<>(path)); collect(node.left, path, paths); collect(node.right, path, paths); path.remove(path.size() - 1); }}hasPathSum(node, target) answers: is there a path from this node down to a leaf that adds up to target?
- null → false.
- remaining = target − node.val.
- Leaf → return remaining == 0.
- Else return hasPathSum(left, remaining) || hasPathSum(right, remaining).
Each node is visited at most once with O(1) work; || may stop early.
Recursion stack: O(log n) when balanced, O(n) for a chain.
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; // no node, no path int remaining = targetSum - root.val; // what the rest of the path must add if (root.left == null && root.right == null) return remaining == 0; // paths end only at leaves return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining); }}Dry run
Carry the running sum next to each node on an explicit stack; check it at every leaf.
- Push (root, root.val).
- Pop; at a leaf, compare the sum with the target.
- Push each child with sum + child.val.
Each node is pushed and popped once.
Waiting siblings plus the current path — on the heap, so even a 10⁵-deep chain is safe.
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; Deque<TreeNode> nodes = new ArrayDeque<>(); Deque<Integer> sums = new ArrayDeque<>(); // root-to-node sum of the node at the same position nodes.push(root); sums.push(root.val); while (!nodes.isEmpty()) { TreeNode node = nodes.pop(); int sum = sums.pop(); if (node.left == null && node.right == null && sum == targetSum) return true; if (node.right != null) { nodes.push(node.right); sums.push(sum + node.right.val); } if (node.left != null) { nodes.push(node.left); sums.push(sum + node.left.val); } } return false; }}in the room
How to say it in the interview
talk track
- Clarify: the path must end at a leaf, values can be negative (so you can't stop when the sum gets big), and an empty tree returns false.
- Say the contract: "hasPathSum(node, t) — is there a node-to-leaf path that adds up to t?" Then the recursion writes itself.
- State O(n) time and O(h) space; offer the explicit-stack version for very deep trees.
traps
- Checking
targetSum == 0when you reachnullinstead of at a leaf: for [1,2] with target 1, the empty right side of 1 would count as a finished path. It isn't one — 1 is not a leaf. - Stopping early once the running sum passes the target: values can be negative, so a later node can bring it back.
what they ask next
Follow-ups
Return the paths themselves (LC 113)?
Path Sum II: keep one path list, add on the way down, remove on the way back, and save a copy at every matching leaf.
What if a path may start and end anywhere, going down (LC 437)?
Path Sum III: prefix sums along the current path, plus a HashMap of how often each one has appeared.
before you submit
Edge cases to test
- Empty tree with target 0 → false.
- [1,2] with target 1 → false: 1 has a child, so it is not a leaf.
- Negative values: [-2,null,-3] with target −5 → true.
practise next
Similar problems
- #113Path Sum IIMediumin Tree Recursion
- #129Sum Root to Leaf NumbersMediumin Tree Recursion
- #437Path Sum IIIMediumin Tree Recursion