Table of contents

Introduction

1.1.

Problem Statement

1.2.

Explanation of the problem

1.3.

Sample Example

Approach to the problem

2.1.

Steps of the algorithm

Iterative Implementation in C++

3.1.

Complexity Analysis

Recursive Implementation in C++

4.1.

Complexity Analysis

Frequently Asked Questions

5.1.

What is a class in C++?

5.2.

What is a queue?

5.3.

What is a pointer?

Conclusion

Last Updated: Mar 27, 2024

Difference between Sums of Odd Level and Even Level Nodes of a Binary Tree

Author Vidhi Singh Java Microservices API

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Binary trees are one of those data structures that allow non-linear storage of data as a collection. Consider it to be something like an array, but the fashion in which elements are stored is very different. Because of the way in which the data is stored, it finds its applications in several situations.

So, in this article, we will discuss a question from the topic Binary Tree: Difference between Sums of Odd Level and Even Level Nodes of a Binary Tree in detail.

Problem Statement

Given a binary tree, you are supposed to write a function that returns the difference between the sum of nodes at the even level and the sum of nodes at the odd level. To erase all the confusion, you need to return the absolute value of the difference.

Explanation of the problem

You will be given a binary tree, you are to return the absolute value of the difference of the sum of the node values at even and odd levels.

By absolute value, it means that the value that we return should be positive. And, this makes us free to start the numbering of the levels with 0 or 1.

Now, what the question means is that we take the sum of all the nodes in the odd levels of the tree and the sum of nodes in the ven levels in the tree. Then, find the difference between these sums.

For instance, if the binary tree is as follows:

Then, the function should return something like this:

Sum of even level nodes = (A+D+E)

Sum od odd level nodes = (B+C)

Absolute difference = |(A+D+E)-(B+C)|

Sample Example

If the actual binary tree is:

The absolute difference is: |(10+8+7)-(15+12)| = |25-27| = |-2| = 2

Approach to the problem

So, the approach to the question is very intuitive and simple as well.

First, we can find the sum of the even level nodes, store them as a variable and then take the sum of the odd level nodes and store them separately. Finally, subtract them to get the required difference.

Now, as we know, nodes of the binary tree can not be accessed randomly. So, we would have to think of some technique through which we can mark the nodes based on their level - whether it is odd or even and then add its value to the sum variable storing even ones or odd ones.

For this, we can take the help of Level Order Traversal of a Binary Tree. Through this, we can keep track of the level at which the node is present.

We keep two variables - sum_odd and sum_even, storing the sum of odd level nodes and the sum of even level nodes respectively. Then, we start traversing the tree in level order. While we are in the even level, we add the node value in the sum_even value, and if we are in the odd level, we add the node value in the sum_odd value. After all the nodes have been traversed, we take the difference of sum_odd and sum_even.

For example,

We start level order traversal, we have defined sum_odd=0 and sum_even=0.

Step 1: We are in the level 0,

sum_even=10

sum_odd=0

Step 2: We are in the level 1,

sum_even=10

sum_odd=15+12=27

Step 3: We are in the level 2,

sum_even=10+(8+7)=25

sum_odd=27

Step 4: Absolute difference=|25-27|=|-2|=2

In order to implement the above approach, we will need a queue. We start with the root, add its value to sum_even and push it into the queue.

Now, we note the size of the queue and start popping the elements from the queue, adding their value to sum_odd push their child nodes to the queue. We pop the nodes equal to the size noted.

After those many elements have been popped, we again note the size of the queue at this point, and pop elements, but add their value to sum_even and push their child nodes o the queue again. This time also, we pop elements equal to the size noted in the first step.

We keep doing like this till all nodes have exhausted. Finally, we make the difference between sum_even and sum_odd and return it.

Steps of the algorithm

Define two variables sum_even=0, sum _odd=0, level=0 and a queue, queue_size=0.
Add the value of the root node to sum_even and push it into the queue.
Store the size of the queue in queue_size.
Update level=1-level
Pop element from the queue and do the following
→ If level=0, add to sum_even, else add to sum_odd.
→ Add its child nodes to the queue.
→ Decrement queue_size.
If queue_size!=0, repeat step 5, else move to step 7.
If the queue is NOT empty, GOTO step 3, else STOP.
Calculate difference |sum_even-sum_odd|.
Return this difference.

Iterative Implementation in C++

#include <bits/stdc++.h>
using namespace std;
 
class node      //Node of the tree
{
    public:
        int val;
        node *left,*right;
};
 
node* new_node(int value)        //Creating a new node
{
    node* t=new node;
    t->val=value;
    t->left=t->right=NULL;
    return t;
}

int difference(node* root)		//Difference function
{
 
    int level=0;
    int sum_even=0,sum_odd=0,queue_size=0;
    queue<node*> q;
    q.push(root);
 
    while(!q.empty())
    {
        int queue_size=q.size();
        level=1-level;
        while(queue_size!=0)
        {
            node* t=q.front();
            q.pop();
            if(level==0)
                sum_even+=t->val;
            else
                sum_odd+=t->val;
         
            if(t->left)
            {
                q.push(t->left);
            }
            if(t->right)
            {
                q.push(t->right);
            }
            queue_size--;
        }
    }
    
    int diff=sum_odd-sum_even; 
    return abs(diff);
}
 
int main()
{
	node* root=new_node(10);
	root->left=new_node(15);
	root->right=new_node(12);
	root->left->left=new_node(8);
	root->left->right=new_node(7);  
	int diff=difference(root);
	cout<<"Difference is "<<diff;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Difference is 2

Complexity Analysis

Time Complexity: O(n)
Here, ‘n’ is the total nodes in the binary tree.

Space Complexity: O(n)
Here, ‘n’ is the total nodes in the binary tree.

The above approach can be executed through recursion in the following way:

Recursive Implementation in C++

#include <bits/stdc++.h>
using namespace std;
 
class node      //Node of the tree
{
    public:
        int val;
        node *left,*right;
};

node* new_node(int value)        //Creating a new node
{
    node* t=new node;
    t->val=value;
    t->left=t->right=NULL;
    return t;
}

void difference(node* parent, int &difference_val,int level)     //Difference function
{
    if(parent==NULL) 
    {
        return;
    }
    if (level&1) 
    {
        difference_val+=parent->val;
    }
    else
    {
        difference_val-=parent->val;
    }
    difference(parent->left,difference_val,level+1);
    difference(parent->right,difference_val,level+1);
}

int main()
{
	node* root=new_node(10);
	root->left=new_node(15);
	root->right=new_node(12);
	root->left->left=new_node(8);
	root->left->right=new_node(7);    
	int diff=0; 
	difference(root,diff,0);
	cout<<"Difference is "<<diff; 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Difference is 2

Complexity Analysis

Time Complexity: O(n)
Here, ‘n’ is the total nodes in the binary tree.

Space Complexity: O(h)
Here, ‘h’ is the height of the binary tree. It is taken up by the recursion stack.

Check out this problem - Two Sum Problem

Frequently Asked Questions

What is a class in C++?

A class is a user-defined data type. It has its own data members and member functions, They can be accessed and used by defining an instance of that class.

What is a queue?

A data structure that stores elements in a linear fashion and elements can be inserted only from the backside and can be deleted only from the front side.

What is a pointer?

A pointer is one of the variables which stores the memory address of another variable. A pointer variable points to a data type of the same type and is created with the * operator.

Conclusion

This article extensively discusses the programming problem: Difference between Sums of Odd Level and Even Level Nodes of a Binary Tree along with their pseudocode, implementation, and time trade-offs

We hope that this blog has helped you enhance your knowledge regarding the Difference between Sum of the Odd Level and Even Level Nodes of a Binary Tree, and if you would like to learn more, check out our articles on Coding Ninjas Blogs.

Recommended problems -

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, SQL, System Design, and many more!

If you want to test your competency in coding, you may check out the Mock Test Series and participate in the Contests organized on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the Problems, Interview Experiences, and Interview Bundle for placement preparations.

Nevertheless, you may consider our Courses to give your career an edge over others!

Do upvote our blog to help other ninjas grow.

Happy Coding!

Live masterclass

Top GenAI Skills to crack 30 LPA+ roles at Amazon & Google

by Sumit Shukla

02 Feb, 2026

03:00 PM

34+ registered

Python + AI Skills to ace 30L+ CTC Data roles at Amazon

by Prerita Agarwal

01 Feb, 2026

06:30 AM

535+ registered

Top 5 GenAI Projects to Crack 25 LPA+ Roles in 2026

by Shantanu Shubham

01 Feb, 2026

08:30 AM

181+ registered

Zero to Data Analyst: Amazon Analyst Roadmap for 30L+ CTC

by Abhishek Soni

02 Feb, 2026

01:30 PM

344+ registered

Top GenAI Skills to crack 30 LPA+ roles at Amazon & Google

by Sumit Shukla

02 Feb, 2026

03:00 PM

34+ registered

Python + AI Skills to ace 30L+ CTC Data roles at Amazon

by Prerita Agarwal

01 Feb, 2026

06:30 AM

535+ registered

View more events