Wednesday, October 17, 2012

hasPathSum - Binary Tree

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values
along the path equals the given sum. Return false if no such path can be found.

So for example, the following tree has exactly four root-to-leaf paths:
                       5
                   /        \
                4           8
              /          /       \         
          11         13        4
         /     \                     \
       7       2                    1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.

/*
 * "root-to-leaf path" to be a sequence of nodes in a tree
 * starting with the root node and proceeding downward to a leaf.
 */
int hasPathSum(nodeptr node, int sum)
{
    int subsum;
    if(node == NULL) {
        return (sum == 0);
    } else {
        subsum = sum - node->data;
        return (hasPathSum(node->left, subsum) ||
                hasPathSum(node->right, subsum));
    }
}

No comments:

Post a Comment