maximum sum of value from root to leaf in a binary tree using stack

Question

I am trying to find the maximum sum of value from root to leaf nodes in a binary tree using stack. I wrote the following code but there is a bug in it . <>

Stacks s;
s.push(root);
maxSum=currSum=0;
      while(!s.isEmpty()) {
        temp = s.top();
        s.pop();
        if( temp->left == null && temp->right == null ) {
          currSum = currSum+temp->data;
          if(currSum > maxSum) {
            maxSum = currSum;
          }
          currSum =0;
        } else {
          currSum = currSum + temp->data;
          if(temp->left) s.push(temp->left);
         if(temp->right) s.push(temp->right);

        }   
      }

What I am trying to do is calculate the sum till the leaf node and assign it to maxSum.
Ex:- Binary tree is

       1
      /   \
    2      3
  /  \
4     5

1)I first push 1 and pop . currSum =1;
2) Push 3 and 2 and pop 2. cursum = 3 and push 5 and 4;
3) Stack now looks like 4<-5-<3-<1 (4 is top element)
4)Now as 4 is leaf node , I enter the if loop and add currSum = 3+4=7 and pop 4 .
5)Now temp is 5 and I set currSum=0, so currSum when I pop 5 becomes 5 .

Can anyone help me fix this bug please

Answer 1

    10
  /   \
 8     2

Consider this example for your code.

1. First root(10) is pushed into the stack and immediately we are popping it.
2. Now the currsum becomes 10 and left (8) and right (2) nodes are pushed into the stack.
3. Now topmost element(2) is popped and added to currsum.Now currsum becomes 12.
4. As we reached leaf node, maxsum contains currsum value.
5. And currsum is made 0.

This is a mistake as we are losing the root value.

6. Now we pop the last element (8) and the currsum has value 8.As we reached leaf node,we compare with maxsum(12) and the final answer is 12 which is wrong.

The Code below will help you through. Try using stack in place of vector.

using namespace std;

struct node {

int data;

struct node* left;

struct node* right;

};


struct node* createNode(int k) {

struct node* temp = new node;

temp->left = NULL;

temp->right = NULL;

temp->data = k;


return temp;


}


int tsum(vector<struct node *> path) {
  int sum;
  int n = path.size();
  int i;
  for (i = 0; i < n; i++)
  sum = sum + path[i]->data;
  return sum;

 }

    int maxsum(struct node *root) {

    int currsum = 0, maxsum = 0;
    vector<struct node *> v;    
    v.push_back(root); //Push root
    vector<int> visited(100, 0);

    while (v.size() > 0) {
    visited[v.back()->data] = 1; //whenever node is reached mark visited

    if (v.back()->left != NULL && !visited[v.back()->left->data])
        v.push_back(v.back()->left);
    else if (v.back()->right != NULL && !visited[v.back()->right->data])
        v.push_back(v.back()->right);
    else {
        if (!v.back()->left && !v.back()->right) {
            currsum = tsum(v);
            if (currsum > maxsum)
                maxsum = currsum;

        }
        v.pop_back(); //pop here is used for backtracking
      }

      }

    return maxsum;
    }


int main() {

int sum = 0;
std::vector<int> arr;
/* Constructed binary node is
       1
     /   \
    2      3
  /  \    
 4     5  
 */
struct node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

int s = 0;

s = maxsum(root);
cout << "SUM" << s << "\n";

return 0;

}