Path Sum in Binary Trees

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

First Solution

Add values recursively as we traverse nodes. Pass the target value as a parameter through the recursion. The main catch is ensuring it’s truly a root-to-leaf path. Leaf nodes must have no children.

bool hasPathSum(TreeNode* root, int sum) {
    if (root==NULL) return false;
    return hasPath(root, 0, sum);
}

bool hasPath(TreeNode* root, int sum, int target) {
    if (!root->left&&!root->right) return sum+root->val==target;
    return ((root->left && hasPath(root->left, sum+root->val, target)) | (root->right && hasPath(root->right, sum+root->val, target)));
}

Cleaner Solution

Think backwards. At leaf nodes, the remaining sum should equal the leaf’s value.

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

#recursion #DFS #tree

Path Sum III: Count All Paths That Sum to Target Powerful Integers: A Brute Force Optimization Lesson