0

Given a Binary Tree, find the maximum sum path from a leaf to root. For example, in the following tree, there are three leaf to root paths 8->-2->10, -4->-2->10 and 7->10. The sums of these three paths are 16, 4 and 17 respectively. The maximum of them is 17 and the path for maximum is 7->10.

              10
             /  \
            -2   7
           /  \     
          8   -4

This is a function to calculate maximum sum from root to any leaf node in the given binary tree. This problem is asked in interview many times by various companies. I am trying this declaring ls and rs as static, but it's producing wrong output. When I'm removing static keyword it's producing correct output.

Can you please explain me what is the problem here with the static keyword.

int roottoleafmaxsum(struct node*temp)  //root will be passed as an argument
{
    static int ls,rs;           //left sum   and   right sum
    if(temp)                     //if temp!=NULL then block will be executed
    {
        ls=roottoleafmaxsum(temp->left);      //recursive call to left
        rs=roottoleafmaxsum(temp->right);     //recursive call to right
        if(ls>rs)
            return (ls+temp->data);           //it will return sum of ls and data   
        else 
            return (rs+temp->data);           //it will return sum of rs and data
    }
}
franiis
  • 1,378
  • 1
  • 18
  • 33
Anuj Garg
  • 584
  • 7
  • 22
  • I think you should return 0 when temp is NULL in your roottoleafmaxsum function. – IronMan007 Jun 14 '16 at 01:48
  • Possible duplicate of [The static keyword and its various uses in C++](https://stackoverflow.com/questions/15235526/the-static-keyword-and-its-various-uses-in-c) – franiis Jun 27 '19 at 07:24

1 Answers1

3

Static means they will retain the value for every function call. Since you are using recursion, it will change the value in the recursive call and that same value will be used in the parent function producing errors.

Cheruvian
  • 5,628
  • 1
  • 24
  • 34
  • That I know but why it is happening in this case?And it is not producing any errors. – Anuj Garg Jul 16 '14 at 18:58
  • It wouldn't produce errors it would just produce the wrong output. It's clear if you walk through it (even on a 3 node tree) why this is. – Cheruvian Jul 16 '14 at 19:04
  • I am not understanding what you are trying to explain. – Anuj Garg Jul 16 '14 at 19:09
  • Instead of initializating to 0 and correctly calculating the path down from each node, ls and rs will initialize to whatever value they were the last timethe function was called. That is why the result is off – Cheruvian Jul 16 '14 at 19:27