Maximum Absolute Difference between any Two Levels of Binary Tree

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Also see, Binary Search Tree

Revisiting Binary Tree 

A binary tree is a data structure where each node can have a maximum number of two children. These child nodes of the binary tree are known as the left child and the right child. 

Prerequisites

To Find the maximum absolute difference between any two levels, a level order traversal of a binary tree is necessary. To know about you can refer to this. 

Problem Statement

The problem states that we are given a binary tree, and we need to calculate the maximum absolute difference between any two levels of a binary tree. The value of nodes of the binary tree can be negative, and the height of the binary tree is greater than two. 

Sample Examples

 Input: Given the binary tree, Find the maximum absolute difference between any two levels.

Output: The maximum absolute difference between any two levels is : 131 
Explanation: 
The sum of level 0 = 49
The Sum of level 1 = 16 + 67 = 83 
The Sum of level 2 = 13 + 21 + 60 + 86 = 180 

Approach

To find the maximum absolute difference between any two levels, we need to find only the minimum and maximum sum levels. Their difference will always give us the maximum absolute difference between any two levels of the binary tree. This can be found by using the level order traversal of the binary tree. At each level, we will check for maximum and minimum sums. 

Algorithm

1. Traverse the binary tree in a level-order fashion using the queue data structure. 
2. We will keep the two variables maxSum and minSum to keep the track of maximum and minimum sum of levels of a binary tree. 
3. We will process the nodes of the binary tree in level order fashion and find the sum of each level, and then compare it with maxSum and minSum.
4. Then return the absolute difference between maxSum and minSum.

Implementation in C++

// C++ program to find the maximum
// absolute difference of level
// sum in Binary Tree
#include <bits/stdc++.h>
using namespace std;

// Class containing left and
// right child of current
// node and key value
class BinaryTreeNode
{
    public:
        int data;
        BinaryTreeNode *left, *right;
        BinaryTreeNode(int data){
            this->data = data;
            left = NULL;
            right = NULL;
        }
};

// Function to find the 
// maximum absolute difference of level
// sum in binary tree
// using level order traversal
int MaximumAbsoluteDifference(BinaryTreeNode *root)
{

   // Initialize value of maximum
   // and minimum level sum
   int maxsum = INT_MIN;
   int minsum = INT_MAX;

   queue<BinaryTreeNode*> q;
   q.push(root);

   // Do Level order traBinaryTreeNodeversal
   // keeping track of number
   // of nodes at every level.
   while (!q.empty())
   {

      // Get the size of queue when
      // the level order traversal
      // for one level finishes
      int s = q.size();

      // Iterate for all the nodes in
      // the queue currently
      int sum = 0;

      for(int i = 0; i < s; i++)
      {

         // Dequeue an node from queue
         BinaryTreeNode*t = q.front();
         q.pop();

         // Add this node's value to
         // the current sum.
         sum += t->data;

         // Enqueue left and
         // right children of
         // dequeued node
         if (t->left != NULL)
            q.push(t->left);

         if (t->right != NULL)
            q.push(t->right);
      }

      // Update the maximum
      // level sum value
      maxsum = max(maxsum, sum);

      // Update the minimum
      // level sum value
      minsum = min(minsum, sum);
   }

   // return the maximum absolute difference 
   // of level sum
   return abs(maxsum - minsum);
}

// Driver code
int main()
{
   BinaryTreeNode *root = new BinaryTreeNode(49);
   root->left = new BinaryTreeNode(16);
   root->right = new BinaryTreeNode(67);
   root->left->left = new BinaryTreeNode(13);
   root->left->right = new BinaryTreeNode(21);
   root->right->left = new BinaryTreeNode(60);
   root->right->right = new BinaryTreeNode(86);

   cout << "The maximum absolute difference between any two levels is " << MaximumAbsoluteDifference(root) << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

The maximum absolute difference between any two levels is 131. 

Complexity Analysis

Time Complexity: O(N)

Explanation: O(N) because we are traveling only the binary tree once for level order traversal. 

Space Complexity: O(N)

Explanation: We are using queue data structure for level order traversal which is taking almost O(N) space. 

Check out this problem - Check If A String Is Palindrome