Given a Binary Tree, write a function getLevelDiff which returns the difference between the sum of nodes at odd level and the sum of nodes at even level
Given a Binary Tree, write a function getLevelDiff which returns the difference between the sum of nodes at odd level and the sum of nodes at even level. The function getLevelDiff takes only one argument, i.e., the root of the binary tree.
1. Initialize two flags, one for even level & other for odd levels.
flago=flag for odd levels
flage=flag for even levels
flago=1,flag e=0
falgo is initialized to 1 because we are starting with root which is considered to be odd level.
2. Initialize two variables, one to store sum of all odd levels & other to store sum of all even levels.
sumo = variable to store sums of all nodes at odd levels
sume = variable to store sums of all nodes at even levels
sumo = 0, sume =0 (initialized)
3. Do a level order traversal being conscious about current level whether odd or even. We can do this using the flags. When flage=1 and flago=0 we are at an even level. So we add the traversed node values with sume. When flago=1 and flage=0 we are at an odd level. So we add the traversed node values with sumo.
We every time push NULL at end of each level & swap values between the flags at end of each level. For example when root is processed (odd level) & we encounter a NULL, we change flage from 0 to 1, flago from 1 to 0 as we are gong to process a even level now Finally we achieve both the sums.
4. Return sumo-sume
Pseudo code:
//initialization
flage=0,flago=1;
queue<node* style="box-sizing: border-box;"> q; //queue for level order traversal
sume=0,sumo=0;
Node* temp;
EnQueue(q,root);
EnQueue(q,NULL);
While (q is not empty){
temp =DeQueue(q);
IF(temp==NULL){
IF(q is not empty){
EnQueue(q,NULL);
}
//change flags
IF(flago){
flage=1;
flago=0;
}
ELSE{
flago=1;
flage=0;
}
}
ELSE{
IF(flage) //at even level
sume+=temp->data;
IF(flago) //at odd level
sumo+=temp->data;
IF(temp->left)
EnQueue(q, temp->left);
IF(temp->right)
EnQueue(q, temp->right);
}
}
return sumo-sume;</node*>
C++ implementation
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data; //value
Node *left; //pointer to left child
Node *right; //pointer to right child
};
// creating new node
Node* newnode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int getLevelDiff(Node *root)
{
//Your code here
int flage=0,flago=1;
queue<Node*> q;
int sume=0,sumo=0;
Node* temp;
q.push(root);
q.push(NULL);
while(!q.empty()){
temp=q.front();
q.pop();
if(temp==NULL){
if(!q.empty()){
q.push(NULL);
}
if(flago){
flage=1;
flago=0;
}
else{
flago=1;
flage=0;
}
}
else{
if(flage)
sume+=temp->data;
if(flago)
sumo+=temp->data;
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
return sumo-sume;
}
int main(){
cout<<"tree is built as per example\n";
Node *root=newnode(1);
root->left= newnode(2);
root->right= newnode(2);
root->right->right=newnode(3);
root->right->left=newnode(4);
root->left->left=newnode(3);
root->left->right=newnode(4);
cout<<"difference between odd & even levels: "<<getLevelDiff(root)<<endl;
return 0;
}
Output
tree is built as per example
difference between odd & even level: 11
Example with explanation
Let the tree be,
1
/ \
2 2
/ \ / \
3 4 4 3
So the odd levels’ sum is = 1+14=15
Even level’s sum is = 4
So the difference is: 11
---------------------------------------------------------
At level 1:
It's odd level
1 is processed
current odd level sum:1
---------------------------------------------------------
At level 2:
It’s even level
2 is processed
current even level sum:2
2 is processed
current even level sum:4
---------------------------------------------------------
At level 3:
It’s odd level
3 is processed
current odd level sum:4
4 is processed
current odd level sum:8
4 is processed
current odd level sum:12
3 is processed
current odd level sum:15
---------------------------------------------------------
Traversal ends
Finally,
Odd level sum=15
Even level sum=4
Difference =15-4=11
Example:
for, the above tree the odd level sum is 3 (root itself) and even level sum is 10 (leaf nodes here) thus the difference is 3-10=-7
Algorithm:
We solve the problem with help of level order traversal.
Function getLevelDiff( Node* root)
1. Initialize two flags, one for even level & other for odd levels.
falgo is initialized to 1 because we are starting with root which is considered to be odd level.
2. Initialize two variables, one to store sum of all odd levels & other to store sum of all even levels.
3. Do a level order traversal being conscious about current level whether odd or even. We can do this using the flags. When flage=1 and flago=0 we are at an even level. So we add the traversed node values with sume. When flago=1 and flage=0 we are at an odd level. So we add the traversed node values with sumo.
We every time push NULL at end of each level & swap values between the flags at end of each level. For example when root is processed (odd level) & we encounter a NULL, we change flage from 0 to 1, flago from 1 to 0 as we are gong to process a even level now
Finally we achieve both the sums.
4. Return sumo-sume
Pseudo code:
C++ implementation
Output
Example with explanation