Path Sum I

110.Path Sum

Tree

Depth-First Search

Problem Statement:

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.

Algorithm:

1. Perform a depth-first search (DFS) on the tree starting from the root.
2. For each node:
   • If the node is a leaf (both left and right children are null), check if the remaining targetSum equals the node's value. Return true if it matches.
   • If not a leaf, recursively check the left and right subtrees, reducing the targetSum by the current node's value.
3. Return true if either subtree has a valid path; otherwise, return false.

Complexity:

Time: O(n), where n is the number of nodes in the tree | Space: O(h), where h is the height of the tree (for recursion stack).

Java Implementation:

public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        // If it's a leaf node, check if the sum matches
        if (root.left == null && root.right == null)
            return targetSum == root.val;

        // Recursively check left and right subtrees
        boolean leftSum = hasPathSum(root.left, targetSum - root.val);
        boolean rightSum = hasPathSum(root.right, targetSum - root.val);

        return leftSum || rightSum;
    }
}
                

Python Implementation:

def hasPathSum(root, targetSum):
    if not root:
        return False

    # If it's a leaf node, check if the sum matches
    if not root.left and not root.right:
        return targetSum == root.val

    # Recursively check left and right subtrees
    leftSum = hasPathSum(root.left, targetSum - root.val)
    rightSum = hasPathSum(root.right, targetSum - root.val)

    return leftSum or rightSum
                

C++ Implementation:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;

        // If it's a leaf node, check if the sum matches
        if (!root->left && !root->right)
            return targetSum == root->val;

        // Recursively check left and right subtrees
        bool leftSum = hasPathSum(root->left, targetSum - root->val);
        bool rightSum = hasPathSum(root->right, targetSum - root->val);

        return leftSum || rightSum;
    }
};