0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Shridhar R Kulkarni Oct 7 '16 at 4:23
  • \$\begingroup\$ It seems fine to me. \$\endgroup\$ – MAG Oct 7 '16 at 4:29
  • \$\begingroup\$ Oops--I misread. My apologies. \$\endgroup\$ – Jerry Coffin Oct 7 '16 at 4:55
1
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ 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)? \$\endgroup\$ – Shridhar R Kulkarni Oct 8 '16 at 1:00
  • \$\begingroup\$ @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. \$\endgroup\$ – vnp Oct 8 '16 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.