# Program to Calculate the Difference Between the Sum of the Odd Level and Even Level Nodes of a Binary Tree

Program to Calculate the Difference Between the Sum of the Odd Level and Even Level Nodes of a Binary Tree on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

## Q. Program to calculate the difference between the sum of the odd level and even level nodes of a Binary Tree.

### Explanation

In this program, we need to calculate the difference between the sum of nodes present at odd levels and sum of nodes present at even levels. Suppose, if a tree contains 5 levels, then

```Difference  = (L1 + L 3 + L5) - (L2 + L4)
```

In the above diagram, odd levels are represented using blue dotted lines and even with green.

```OddLevelSum = 1 + 4 + 5 + 6 = 16
EvenLevelSum = 2 + 3 = 5
Difference = |16 - 5| = 11
```

### Algorithm

1. Define Node class which has three attributes namely: data, left, and right. Here, left represents the left child of the node and right represents the right child of the node.
2. When a node is created, Assign the data part of a node with an appropriate value having its left and right child as NULL.
3. Define another class which has an attribute root.
1. Root represents the root node of the tree having null value initially.
4. The difference() will calculate the difference between the sum of nodes at the odd and even levels:
1. Traverse through the binary tree level wise using Queues.
2. Keep track of current level using the variable currentLevel.
3. If the currentLevel is divisible by 2, then add all the values of nodes present in currentLevel to variable evenLevel. Else, add all the values of nodes to variable oddLevel.
4. Calculate the difference by subtracting value present in evenLevel from oddLevel.

### Python

```#Represent a node of binary tree
class Node:
def __init__(self,data):
#Assign data to the new node, set left and right children to None
self.data = data;
self.left = None;
self.right = None;

class DiffOddEven:
def __init__(self):
#Represent the root of binary tree
self.root = None;

#difference() will calculate the difference between sum of odd and even levels of binary tree
def difference(self):
oddLevel = 0;
evenLevel = 0;
diffOddEven = 0;

#Variable nodesInLevel keep tracks of number of nodes in each level
nodesInLevel = 0;

#Variable currentLevel keep track of level in binary tree
currentLevel = 0;

#queue will be used to keep track of nodes of tree level-wise
queue = [];

#Check if root is None
if(self.root == None):
print("Tree is empty");
return 0;
else:
#Add root node to queue as it represents the first level
queue.append(self.root);
currentLevel = currentLevel + 1;

while(len(queue) != 0):
#Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
nodesInLevel = len(queue);

while(nodesInLevel > 0):
current = queue.pop(0);

#Checks if currentLevel is even or not.
if(currentLevel % 2 == 0):
#If level is even, add nodes's to variable evenLevel
evenLevel = evenLevel + current.data;
else:
#If level is odd, add nodes's to variable oddLevel
oddLevel = oddLevel + current.data;

if(current.left != None):
queue.append(current.left);
if(current.right != None):
queue.append(current.right);
nodesInLevel = nodesInLevel - 1;
currentLevel = currentLevel + 1;
#Calculates difference between oddLevel and evenLevel
diffOddEven = abs(oddLevel - evenLevel);
return diffOddEven;

bt = DiffOddEven();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.right.left = Node(5);
bt.root.right.right = Node(6);

#Display the difference between sum of odd level and even level nodes
print("Difference between sum of odd level and even level nodes: " + str(bt.difference()));
```

Output:

```Difference between sum of odd level and even level nodes: 11
```

### JAVA

```import java.util.LinkedList;
import java.util.Queue;

public class DiffOddEven {

//Represent a node of binary tree
public static class Node{
int data;
Node left;
Node right;

public Node(int data){
//Assign data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}

//Represent the root of binary tree
public Node root;

public DiffOddEven(){
root = null;
}

//difference() will calculate the difference between sum of odd and even levels of binary tree
public int difference() {
int oddLevel = 0, evenLevel = 0, diffOddEven = 0;

//Variable nodesInLevel keep tracks of number of nodes in each level
int nodesInLevel = 0;

//Variable currentLevel keep track of level in binary tree
int currentLevel = 0;

//Queue will be used to keep track of nodes of tree level-wise

//Check if root is null
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
//Add root node to queue as it represents the first level
currentLevel++;

while(queue.size() != 0) {

//Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
nodesInLevel = queue.size();

while(nodesInLevel > 0) {
Node current = queue.remove();

//Checks if currentLevel is even or not.
if(currentLevel % 2 == 0)
//If level is even, add nodes's to variable evenLevel
evenLevel += current.data;
else
//If level is odd, add nodes's to variable oddLevel
oddLevel += current.data;

if(current.left != null)
if(current.right != null)
nodesInLevel--;
}
currentLevel++;
}
//Calculates difference between oddLevel and evenLevel
diffOddEven = Math.abs(oddLevel - evenLevel);
}
return diffOddEven;
}

public static void main (String[] args) {

DiffOddEven bt = new DiffOddEven();
//Add nodes to the binary tree
bt.root = new Node(1);
bt.root.left = new Node(2);
bt.root.right = new Node(3);
bt.root.left.left = new Node(4);
bt.root.right.left = new Node(5);
bt.root.right.right = new Node(6);

//Display the difference between sum of odd level and even level nodes
System.out.println("Difference between sum of odd level and even level nodes: " + bt.difference());
}
}
```

Output:

```Difference between sum of odd level and even level nodes: 11
```

### C#

```using System;
using System.Collections.Generic;
namespace Tree
{
public class Program
{
//Represent a node of binary tree
public class Node<T>{
public T data;
public Node<T> left;
public Node<T> right;

public Node(T data) {
//Assign data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}

public class DiffOddEven<T>{
//Represent the root of binary tree
public Node<T> root;

T[] treeArray;
int index = 0;

public DiffOddEven(){
root = null;
}

//difference() will calculate the difference between sum of odd and even levels of binary tree
public int difference() {
int oddLevel = 0, evenLevel = 0, diffOddEven = 0;

//Variable nodesInLevel keep tracks of number of nodes in each level
int nodesInLevel = 0;

//Variable currentLevel keep track of level in binary tree
int currentLevel = 0;

//Queue will be used to keep track of nodes of tree level-wise
Queue<Node<T>> queue = new Queue<Node<T>>();

//Check if root is null
if(root == null) {
Console.WriteLine("Tree is empty");
return 0;
}
else {
//Add root node to queue as it represents the first level
queue.Enqueue(root);
currentLevel++;

while(queue.Count != 0) {

//Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
nodesInLevel = queue.Count;

while(nodesInLevel > 0) {
Node<T> current = queue.Dequeue();

//Checks if currentLevel is even or not.
if(currentLevel % 2 == 0)
//If level is even, add nodes's to variable evenLevel
evenLevel += Convert.ToInt32(current.data);
else
//If level is odd, add nodes's to variable oddLevel
oddLevel += Convert.ToInt32(current.data);

if(current.left != null)
queue.Enqueue(current.left);
if(current.right != null)
queue.Enqueue(current.right);
nodesInLevel--;
}
currentLevel++;
}
//Calculates difference between oddLevel and evenLevel
diffOddEven = Math.Abs(oddLevel - evenLevel);
}
return diffOddEven;
}
}

public static void Main()
{
DiffOddEven<int> bt = new DiffOddEven<int>();
//Add nodes to the binary tree
bt.root = new Node<int>(1);
bt.root.left = new Node<int>(2);
bt.root.right = new Node<int>(3);
bt.root.left.left = new Node<int>(4);
bt.root.right.left = new Node<int>(5);
bt.root.right.right = new Node<int>(6);

//Display the difference between sum of odd level and even level nodes
Console.WriteLine("Difference between sum of odd level and even level nodes: " + bt.difference());
}
}
}
```

Output:

```Difference between sum of odd level and even level nodes: 11
```

### PHP

```<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
public \$data;
public \$left;
public \$right;

function __construct(\$data){
//Assign data to the new node, set left and right children to NULL
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}

class DiffOddEven{
//Represent the root of binary tree
public \$root;
function __construct(){
\$this->root = NULL;
}

//difference() will calculate the difference between sum of odd and even levels of binary tree
function difference(){
\$oddLevel = 0;
\$evenLevel = 0;
\$diffOddEven = 0;

//Variable nodesInLevel keep tracks of number of nodes in each level
\$nodesInLevel = 0;

//Variable currentLevel keep track of level in binary tree
\$currentLevel = 0;

//queue will be used to keep track of nodes of tree level-wise
\$queue = array();

//Check if root is null
if(\$this->root == NULL) {
print("Tree is empty <br>");
return 0;
}
else {
//Add root node to queue as it represents the first level
array_push(\$queue,\$this->root);
\$currentLevel++;

while(sizeof(\$queue) != 0) {

//Variable nodesInLevel will hold the size of queue i.e. number of elements in queue
\$nodesInLevel = sizeof(\$queue);
while(\$nodesInLevel > 0) {
\$current = array_shift(\$queue);

//Checks if currentLevel is even or not.
if(\$currentLevel % 2 == 0)
//If level is even, add nodes's to variable evenLevel
\$evenLevel += \$current->data;
else
//If level is odd, add nodes's to variable oddLevel
\$oddLevel += \$current->data;

if(\$current->left != NULL)
array_push(\$queue, \$current->left);
if(\$current->right != NULL)
array_push(\$queue, \$current->right);
\$nodesInLevel--;
}
\$currentLevel++;
}
//Calculates difference between oddLevel and evenLevel
\$diffOddEven = abs(\$oddLevel - \$evenLevel);
}
return \$diffOddEven;
}
}

\$bt = new DiffOddEven();
//Add nodes to the binary tree
\$bt->root = new Node(1);
\$bt->root->left = new Node(2);
\$bt->root->right = new Node(3);
\$bt->root->left->left = new Node(4);
\$bt->root->right->left = new Node(5);
\$bt->root->right->right = new Node(6);

//Display the difference between sum of odd level and even level nodes
print "Difference between sum of odd level and even level nodes: " . \$bt->difference();
?>
</body>
</html>
```

Output:

```Difference between sum of odd level and even level nodes: 11
```

Next TopicPrograms List