Java Program to calculate the Difference between the Sum of the Odd Level and the Even Level Nodes of a Binary Tree

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

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

Algorithm

• 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.
• When a node is created, Assign the data part of a node with an appropriate value having its left and right child as NULL.
• Define another class which has an attribute root.
  • Root represents the root node of the tree having null value initially.

a. The difference() will calculate the difference between the sum of nodes at the odd and even levels:

• Traverse through the binary tree level wise using Queues.
• Keep track of current level using the variable currentLevel.
• 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.
• Calculate the difference by subtracting value present in evenLevel from oddLevel.

Program:

Output:

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