Path Sum

easy tree dfs recursion

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.

Carry the running total down the recursion. At a leaf, check whether the remaining target equals the leaf's value. The recursive form is hasPath(node, t) = hasPath(left, t − node.val) ∨ hasPath(right, t − node.val).

Inputtree: [5, 4, 8, 11, _, 13, 4, 7, 2], target: 22

Outputtrue

Path 5 → 4 → 11 → 2 sums to 22.

level-order ('_' for null)

target

def has_path_sum(root, target):
    if root is None:
        return False
    if root.left is None and root.right is None:
        return target == root.val
    rem = target - root.val
    return has_path_sum(root.left, rem) or has_path_sum(root.right, rem)

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

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

bool hasPathSum(TreeNode* root, int target) {
    if (!root) return false;
    if (!root->left && !root->right) return target == root->val;
    int rem = target - root->val;
    return hasPathSum(root->left, rem) || hasPathSum(root->right, rem);
}

Explanation

We just need a yes/no answer: does some root-to-leaf path add up to the target? The cleanest way is recursion that shrinks the target as it walks down, rather than adding values up.

At each node we subtract its value from the target we still need. We pass that smaller remainder, rem = target - node.val, down into both children. By the time we reach a leaf, the question becomes simple.

The base case is the leaf check: if a node has no children, we return whether target == node.val — meaning the running remainder exactly lands on this leaf's value. Empty spots return false.

The two child calls are joined with or, so a single matching path anywhere makes the whole thing true. Once one branch succeeds, that true bubbles straight back up.

Example: target 22 on the sample tree. Going 5 → 4 → 11 → 2, the remainder becomes 17 → 13 → 2, and at leaf 2 the remaining 2 matches, so the answer is true.

Time: O(n) Space: O(h) recursion depth