5.11 Path Sum

5.11.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 112
• Difficulty: Easy
• URL: https://leetcode.com/problems/lc-path-sum/
• Tags:
• Techniques: Depth First Search, Tree

5.11.2 Description

Determine if a binary tree has a root-to-leaf path whose node values sum to a target.

5.11.3 Examples

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

5.11.4 Constraints

• 0 <= nodes <= 5000

5.11.5 Solution - DFS with Running Sum

5.11.5.1 Walkthrough

Traverse the tree, accumulating the current sum along the path. When a leaf is reached, check if the sum equals the target. Short-circuit as soon as a valid path is found.

5.11.5.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.11.5.3 Code - Java

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