Get difference between values at Even and Odd level in a binary tree

Question:

Given a binary tree, get the difference of the sum of the nodes at odd level and sum of the nodes at even level.

Example:

Consider the image given below:

Form the image above,

The sum of nodes at odd level is 16 + 7 + 15 + 18 + 30 = 86

The sum of nodes at even level is 10 + 25 = 35

So the output should be 86 – 35 = 51

Solution:

This problem can be solved by recursive traversal.

Assume if you have only one node, and no left and right node.

Now, you will do
root – left_node – right_node
= 16 – 0 – 0 = 16

Suppose,
if you have left and right children as shown below:

root – left_node – right_node

= 16 – 10 – 25 = -19

We apply similar logic to all the nodes.

return root->data – get_level_diff(root->left) – get_level_diff(root->right);

We call “get_level_diff” recursively for left and right nodes, and arrive at the solution.

Recursion Visualization:

As we are calling the “get_level_diff” recursively, let us understand how it will work:

We take an empty stack, and stack will grow as follows:

So we perform similar recursive call to all the nodes and arrive at our solution.

Solution in C++

#include <iostream>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


int get_level_diff(Node *root)  
{  
// Base case  
if (root == NULL)  
        return 0;  
 
return root->data - get_level_diff(root->left) -  
                    get_level_diff(root->right);  
}  
  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"Solution = " << get_level_diff(root)<<endl; 

    return 0;  
}  

 

Output:

Solution = 51