Home » Interview coding problems/challenges

Odd even level difference in a binary tree

In this article, we are going to see how to find the difference between sums of odd and even levels of a binary tree? This problem has been featured in interview rounds of Amazon. Submitted by Radib Kar, on January 29, 2019

Problem statement

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.

Solution

Example

 3
/ \
4  6

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.

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 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;

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