Root to leaf path with given sum in binary tree

Question

For a given binary tree and a sum, I have written the following function to check whether there is a root to leaf path in that tree with the given sum.

/* 
//A binary tree node
struct Node
{
 int data;
 struct Node* left, * right;
}; 
*/
bool hasPathSum(Node *node, int sum)
{
 if(!node)
 return sum==0;
 return ( hasPathSum(node->left, sum-node->data) || 
 hasPathSum(node->right, sum-node->data) );
}

Are there any edge cases in which the code will break? Also, do comment on the code style.

• Shridhar R Kulkarni: @JerryCoffin: The sum==0 statement is reached only when node==NULL. Otherwise hasPathSum is recursively called on left and right subtree until it reaches left or right subtree of a leaf node.
• MAG: It seems fine to me.
• Jerry Coffin: Oops--I misread. My apologies.

Answer 1

• Give your operators some breathing space.

   if (!node) {
   return sum == 0;
   }
   return hasPathSum(node->left, sum - node->data) || 
   hasPathSum(node->right, sum - node->data);
  

  Note that return expression needs no parenthesis.

• sum - node->data seems more natural to be expressed once:

   sum -= node->data;
   return hasPathSum(node->left, sum) || 
   hasPathSum(node->right, sum);
  

• I see no edge cases except possible overflows.

• Shridhar R Kulkarni: Thanks, henceforth I will see to it that operators get space to breathe. I see in your code you have omitted the parenthesis in return statement and added braces for if construct. Will you suggest me how do I decide whether to use/omit braces in the code(of course in cases where it is not necessary to use them), whether I should use/omit the parenthesis(again when they are not necessary to be used)?
• vnp: @shridharfly It is generally recommended to never omit braces. Parenthesis OTOH are less strict. Use them to emphasize the priority of subexpressions. Parenthesis around an entire expression are never used; particularly with return expression.