jain12

level having maximum sum in a binary tree

Feb 29th, 2020
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4.  
  5. class Node{
  6.   public:
  7.       int data;
  8.       Node *left,*right;
  9.       Node(int key){
  10.         data=key;
  11.         left=NULL;
  12.         right=NULL;
  13.         }
  14.   };
  15.  
  16. int MaximumSumLevel(Node *root){
  17. if(root==NULL)
  18.    return 0;
  19. queue<Node*>q;
  20. int max_sum=INT_MIN,curr_sum=0,max_sum_level=0,curr_level=0;
  21. q.push(root);
  22. q.push(NULL);
  23. while(!q.empty()){
  24.   Node *temp=q.front();
  25.   q.pop();
  26.   if(temp!=NULL){
  27.      curr_sum=curr_sum+temp->data;
  28.     if(temp->left!=NULL)
  29.         q.push(temp->left);
  30.     if(temp->right!=NULL)
  31.         q.push(temp->right);
  32.     }
  33.    else{
  34.         curr_level++;
  35.         if(max_sum<curr_sum){
  36.             max_sum=curr_sum;
  37.             max_sum_level=curr_level;
  38.             }
  39.         curr_sum=0;
  40.         if(q.size()>0)
  41.           q.push(NULL);
  42.     }
  43.    }
  44.    cout<<"maximum sum is "<<max_sum;
  45. return max_sum_level;
  46.   }
  47.  
  48. int main(){
  49.   Node *root1=NULL;
  50.   Node *newnode=new Node(1);
  51.   root1=newnode;
  52.   root1->left=new Node(2);
  53.   root1->right=new Node(3);
  54.   (root1->left)->left=new Node(4);
  55.   (root1->right)->right=new Node(5);
  56.   ((root1->left)->left)->left=new Node(6);
  57.   cout<<endl<<"level is "<<MaximumSumLevel(root1);
  58.   return 0;
  59.   }
Add Comment
Please, Sign In to add comment