Path Sum Easy 0 attempts
LeetCode ↗

Path Sum

Easy TreeBinary TreeDFS LeetCode

You're given the root of a binary tree and a target sum. Work out whether there's a path starting at the root and ending at a leaf whose node values add up exactly to that target.

Input Format
Implement hasPathSum(root, targetSum). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
root = [1,2,3]
targetSum = 5
Output
false
Constraints
  • 0 <= number of nodes <= 5000
  • -1000 <= Node.val, targetSum <= 1000
Test Cases (2)
Case 1
Args: [[5,4,8,11,null,13,4,7,2,null,null,null,1],22] Expected: true
Case 2
Args: [[1,2,3],5] Expected: false
Topics
TreeBinary TreeDFS

DFS

javascript
function hasPathSum(root, targetSum) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === targetSum;
  const remaining = targetSum - root.val;
  return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.

JavaScript