## 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.