Has Path Sum (binary tree)

Given a Binary Tree and a number x, Write a function to see if there exist a root to leaf path in the tree whose sum is equal to x.

Solution:

For Example: Let us consider the below tree:

There are only three root to leaf paths in the tree

1. 10 – 5 – 4 – 1
2. 10 – 5 – 8
3. 10 – 30 – 40

Algorithm:

If x = 20, then the problem “find a path in the tree (with root at 10), whose sum is 20” can be broken into

• Find a path in the tree with root at 5, whose sum is 10 (20 – 10).
• Find a path in the tree with root at 30, whose sum is 10 (20 – 10).

We will return true if any of the below recursive call returns true.

Code:

The below function will return true if there exist a path in the tree with sum = x, else it will return false.

/* returns true if there exists a path in the tree whose sum = x */
bool hasPathSum(node* r, int x){
     // If null tree and x == 0 then return true
     if(0 == x)
         return r ? false : true;
     if(r)
     {
          // If leaf node then its data should be x
          if ( NULL == r->left && NULL == r->right )
               return !(x – r->data);
          // If only right sub-tree then check in right only
          if(NULL == r->left)
               return hasPathSum(r->right, x – r->data);
          // If only LEFT sub-tree then check in left only
          if(NULL == r->right)
               return hasPathSum(r->left, x – r->data);
          // Check both left & right sub trees
          return ( hasPathSum(r->left, x – r->data) ||
               hasPathSum(r->right, x – r->data) );
     }
     else
          return false;
}