Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Explanation of the problem 
1.3.
Sample Example
2.
Approach to the problem 
2.1.
Steps of the algorithm 
3.
Iterative Implementation in C++
3.1.
Complexity Analysis
4.
Recursive Implementation in C++
4.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is a class in C++? 
5.2.
What is a queue?
5.3.
What is a pointer?
6.
Conclusion
Last Updated: Mar 27, 2024

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

Author Vidhi Singh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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

  1. Define two variables sum_even=0sum _odd=0, level=0 and a queue, queue_size=0
  2. Add the value of the root node to sum_even and push it into the queue. 
  3. Store the size of the queue in queue_size
  4. Update level=1-level
  5. 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.
  6. If queue_size!=0, repeat step 5, else move to step 7.
  7. If the queue is NOT empty, GOTO step 3, else STOP.
  8. Calculate difference |sum_even-sum_odd|.
  9. Return this difference. 
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

 

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

 

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 AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem 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 ProblemsInterview 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!

Previous article
Check if a Binary Tree is an Even-Odd Tree or Not
Next article
Print Alternate Nodes from all Levels of a Binary Tree
Live masterclass