current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 0 down vote favorite

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.

share|improve this question
    
@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. – shridharfly Oct 7 '16 at 4:23
    
It seems fine to me. – MAG Oct 7 '16 at 4:29
    
Oops--I misread. My apologies. – Jerry Coffin Oct 7 '16 at 4:55
up vote 2 down vote accepted

  • 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.

share|improve this answer
    
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)? – shridharfly Oct 8 '16 at 1:00
    
@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. – vnp Oct 8 '16 at 3:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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