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

Binary trees are fundamental data structures used in computer science and programming. They consist of nodes connected by edges, forming a hierarchical structure. In this article, we will explore a C++ program that calculates the difference between the sum of the odd-level and even-level nodes of a binary tree. We will also provide examples to illustrate the program’s functionality.

Understanding the Problem

To solve this problem, we need to traverse the binary tree and calculate the sum of the nodes at odd levels and even levels separately. The difference between these two sums will give us the desired result.

Approach

To implement this program, we will use a recursive approach known as depth-first search (DFS). The algorithm will traverse the tree in a pre-order fashion, meaning it visits the current node first, then its left child, and finally its right child.

Let’s take a look at the implementation:

#include <iostream>
using namespace std;

// Definition of a Binary Tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

int calculateDifference(TreeNode* node, int level) {
    if (node == nullptr)
        return 0;

    // If the current level is odd, add the node's value
    // Otherwise, subtract the node's value
    int diff = (level % 2 == 1) ? node->val : -node->val;

    // Recursively calculate the difference for left and right subtrees
    diff += calculateDifference(node->left, level + 1);
    diff += calculateDifference(node->right, level + 1);

    return diff;
}

int main() {
    // Creating a binary tree
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(2);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(3);

    // Calculate the difference between the sum of odd and even level nodes
    int difference = calculateDifference(root, 1);

    cout << "Difference between sum of odd and even level nodes: " << difference << endl;

    return 0;
}

Explanation

1. We start by defining the TreeNode struct, representing each node in the binary tree. It contains an integer value, as well as pointers to its left and right children.
2. The calculateDifference function takes in the current node and the level as parameters. It returns the difference between the sum of odd and even level nodes.
3. Inside the calculateDifference function, we first handle the base case: if the current node is nullptr, we return 0.
4. Next, we determine whether the current level is odd or even. If it’s odd, we add the node’s value to the difference; otherwise, we subtract it.
5. We recursively call the calculateDifference function for the left and right subtrees, passing the updated level.
6. Finally, we calculate the difference by summing the differences from the left and right subtrees, and return it.
7. In the main function, we create a sample binary tree and call the calculateDifference function with the root node and the initial level of 1.
8. We store the calculated difference in the difference variable and display it on the console.

For the provided binary tree, the program will output:

Difference between sum of odd and even level nodes: -4

Explanation of the Example

In the given binary tree, the odd-level nodes are: 5, 1, and 7, with a sum of 13. The even-level nodes are: 2, 6, 4, and 3, with a sum of 17. Therefore, the difference between the sum of odd and even level nodes is 13 – 17 = -4.

Conclusion

We have discussed a C++ program to calculate the difference between the sum of the odd level and even level nodes of a binary tree. By using a depth-first search (DFS) approach, we traverse the tree and compute the sum of nodes at odd and even levels separately. The resulting difference provides insight into the tree’s structure and can be useful in various applications. Feel free to use and modify this program to suit your specific needs in binary tree analysis or related tasks.