CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to calculate the difference between the sum of the odd level and even level nodes of a Binary Tree.ExplanationIn 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
SolutionPython#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 levelwise 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 levelwise 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 JAVAimport 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 levelwise 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 levelwise 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 levelwise $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
Next TopicPrograms List
