## 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

- Traverse the binary tree in a level-order fashion using the queue data structure.
- We will keep the two variables maxSum and minSum to keep the track of maximum and minimum sum of levels of a binary tree.
- 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.
- 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;
}
```

**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__