Skip to main content

112. Path Sum

easy

Determine whether a binary tree has any root-to-leaf path whose values sum to a target. The classic 'subtract and recurse' decomposition.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

Examples

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 the target sum is 5 -> 4 -> 11 -> 2 = 22.

Example 2

Input
root = [1,2,3], targetSum = 5
Output
false

Example 3

Input
root = [], targetSum = 0
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Empty tree returns false (the problem says 0 for empty).

Hint 2

At a leaf node, just check whether the node's value equals the remaining target.

Hint 3

Recurse: hasPath(node, target) = hasPath(node.left, target - node.val) OR hasPath(node.right, target - node.val).

Solution approach

Reveal approach

Recursive subtract-and-descend. If node is null, return false (covers both empty tree and walking past a leaf). If node is a leaf (no children), return node.val == targetSum. Otherwise return hasPath(node.left, targetSum - node.val) OR hasPath(node.right, targetSum - node.val). The early-OR short-circuits as soon as a valid path is found. O(n) time, O(h) recursion space.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dfs
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Path Sum and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →