Q:

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

belongs to collection: Tree Programs

0

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.

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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;  
                          
                    #Adds left child to queue  
                    if(current.left != None):  
                        queue.append(current.left);  
                    #Adds right child to queue  
                    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

 

C

#include <stdio.h>  
#include <stdlib.h>  
   
//Represent a node of binary tree  
struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};  
   
//Represent the root of binary tree  
struct node *root = NULL;  
   
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode, set left and right child to NULL  
    newNode->data = data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
      
    return newNode;  
}  
   
//Queue will be used to keep track of nodes of tree level-wise  
struct node *queue[100];  
int rear = 0, front = -1, size = 0;  
   
//Adds a node to queue  
void enqueue(struct node *temp){  
    queue[rear++] = temp;  
    size++;  
}  
   
//Deletes a node from queue  
struct node *dequeue(){  
    size--;  
    return queue[++front];  
}  
   
//difference() will calculate the difference between sum of odd and even levels of binary tree  
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;  
      
    //Check if root is null  
    if(root == NULL) {  
        printf("Tree is empty\n");  
        return 0;  
    }  
    else {  
        //Add root node to queue as it represents the first level  
        enqueue(root);  
        currentLevel++;  
          
        while(size != 0) {  
                
            //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue  
            nodesInLevel = size;  
              
            while(nodesInLevel > 0) {  
                  struct node *current = dequeue();  
                    
                //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;  
                    
                //Adds left child to queue  
                if(current->left != NULL)  
                    enqueue(current->left);  
                //Adds right child to queue  
                if(current->right != NULL)   
                    enqueue(current->right);  
                nodesInLevel--;  
            }  
            currentLevel++;  
        }  
        //Calculates difference between oddLevel and evenLevel  
        diffOddEven = abs(oddLevel - evenLevel);  
    }  
    return diffOddEven;  
  }  
      
int main(){  
      
    //Add nodes to the binary tree  
    root = createNode(1);  
    root->left = createNode(2);  
    root->right = createNode(3);  
    root->left->left = createNode(4);  
    root->right->left = createNode(5);  
    root->right->right = createNode(6);  
      
    //Display the difference between sum of odd level and even level nodes  
    printf("Difference between sum of odd level and even level nodes: %d", difference());  
      
    return 0;  
}  

 

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  
          Queue<Node> queue = new LinkedList<Node>();  
            
          //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  
              queue.add(root);  
              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;  
                        
                      //Adds left child to queue  
                      if(current.left != null)  
                          queue.add(current.left);  
                      //Adds right child to queue  
                      if(current.right != null)   
                          queue.add(current.right);  
                     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);  
                            
                            //Adds left child to queue  
                            if(current.left != null)  
                                queue.Enqueue(current.left);  
                            //Adds right child to queue  
                            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;  
                    
                    //Adds left child to queue  
                    if($current->left != NULL)  
                        array_push($queue, $current->left);  
                    //Adds right child to queue  
                    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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Program to construct a Binary Search Tree and perf... >>