LeetCode 112 – Path Sum: Problem Description, Analysis, and Solutions in Java, C++, and Python

Problem Description : Given the root of a binary tree and an integer targetSum, determine if there exists a root‑to‑leaf path such that the sum of the node values along the path equals targetSum. Return true if such a path exists, otherwise false.

Example 1 : Input:

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

Output: true Explanation: The path 5→4→11→2 sums to 22.

Example 2 : Input: root = [1,2,3], targetSum = 5 Output: false Explanation: The two root‑to‑leaf paths have sums 3 and 4, none equal to 5.

Constraints :

Number of nodes is in the range [0, 5000].

-1000 ≤ Node.val ≤ 1000.

-1000 ≤ targetSum ≤ 1000.

Problem Analysis : The solution uses recursion, subtracting the current node's value from targetSum as we traverse down the tree. When a leaf node is reached, we check whether the remaining sum equals the leaf's value. If any recursive call returns true, the required path exists.

Java Solution :

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null)
        return false;
    // leaf node check
    if (root.left == null && root.right == null && targetSum == root.val)
        return true;
    // recurse on children with updated sum
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

C++ Solution :

bool hasPathSum(TreeNode *root, int targetSum) {
    if (root == nullptr)
        return false;
    // leaf node check
    if (root->left == nullptr && root->right == nullptr && targetSum == root->val)
        return true;
    // recurse on children with updated sum
    return hasPathSum(root->left, targetSum - root->val)
        || hasPathSum(root->right, targetSum - root->val);
}

Python Solution :

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    if not root:
        return False
    # leaf node check
    if not root.left and not root.right:
        return targetSum == root.val
    # recurse on children with updated sum
    return (self.hasPathSum(root.left, targetSum - root.val) or
            self.hasPathSum(root.right, targetSum - root.val))