Path Sum | Problems | DailyCoder

Given a binary tree and a target sum, determine if the tree has a root-to-leaf path where the values sum to the target.

Example: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22 → true (5→4→11→2)

Sample Input

—

Sample Output

—

Constraints

0 <= number of nodes <= 5000
-1000 <= Node.val, targetSum <= 1000

Topics

Tree Binary Tree DFS

DFS

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.