Command Palette

Search for a command to run...

Hectal
Problem 16.9 · Binary TreesEasy

Path Sum

PatternTree DFS

What it teaches: Pass information down (the remaining sum) and check at the leaves.

Practise it on judges as “Path Sum”.

The problem

Return true if some root-to-leaf path adds up to targetSum.

Example 1

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

5 → 4 → 11 → 2.

Constraints

  • 0 ≤ nodes ≤ 5000
  • −1000 ≤ values, target ≤ 1000

Pattern clues in the wording

  • → Root-to-leaf paths with a running total

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22
true
2
root = [1,2,3]
targetSum = 5
false
3
root = []
targetSum = 0
false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Pre-order with a remaining sum · O(n)
1

Pre-order with a remaining sum

Time O(n) Space O(h)

hasPathSum(n, rem): null → false; at a leaf, return rem == n.val; else recurse on both children with rem − n.val.

Approach 1
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;
        int rem = targetSum - root.val;
        return hasPathSum(root.left, rem) || hasPathSum(root.right, rem);
    }
}

Verdict: Simple top-down recursion.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty tree → false (even for target 0)
  • Negative values
  • Path must end at a leaf

Mistakes people make

  • Stopping at a non-leaf node whose prefix matches the target.

Interview

Follow-up questions

How would you count all downward paths (not just root-to-leaf) with the sum?