Root to leaf path sum equal to a given number - GeeksforGeeks

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

/*

 Given a tree and a sum, return true if there is a path from the root

 down to a leaf, such that adding up all the values along the path

 equals the given sum.

 

 Strategy: subtract the node value from the sum when recurring down,

 and check to see if the sum is 0 when you run out of tree.

*/

bool hasPathSum(struct node* node, int sum)

{

  /* return true if we run out of tree and sum==0 */

  if (node == NULL)

  {

     return (sum == 0);

  }

  

  else

  {

    bool ans = 0; 

  

    /* otherwise check both subtrees */

    int subSum = sum - node->data;

  

    /* If we reach a leaf node and sum becomes 0 then return true*/

    if ( subSum == 0 && node->left == NULL && node->right == NULL )

      return 1;

  

    if(node->left)

      ans = ans || hasPathSum(node->left, subSum);

    if(node->right)

      ans = ans || hasPathSum(node->right, subSum);

  

    return ans;

  }

}

Read full article from Root to leaf path sum equal to a given number - GeeksforGeeks