How to Find a Root‑to‑Leaf Path Matching a Target Sum in a Binary Tree

Description

Given a binary tree and an integer target sum, determine whether there exists a path from the root node to any leaf node such that the sum of the node values along that path equals the target sum. A leaf is defined as a node without children, and the path must terminate at a leaf.

Analysis

The algorithm subtracts the current node's value from the remaining target sum while traversing from the root. When a leaf node is reached, the remaining sum is checked; if it is zero, a valid path has been found. The process recurses on left and right sub‑trees.

Solution

bool hasPathSum(struct TreeNode *root, int sum) {
    if (root == NULL) {
        return false;
    }
    sum -= root->val;
    if (root->left == NULL && root->right == NULL) {
        return sum == 0;
    } else {
        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
    }
}