Introduction
In this blog, we are going to discuss a very interesting problem in the binary tree where we need to find all minimum values that must be added at every level in the given binary tree such that the sum of the nodes at every level becomes equal.
Let us recall what is a binary tree.
A binary tree comprises several nodes-each containing left and right pointers and a data item. While the left and the right pointers point to the subtrees recursively, the root pointer points to the tree's topmost node.
Owing to repetition in their structure, binary tree problems often require recursion to perform the given task. A null pointer either represents the trees if they are empty or by a single node's left and right pointers. Conventionally, the left child nodes in a binary tree must be less than or equal to the parent node; and the right child nodes must be equal to or greater than their parent node.
Also see, Data Structures
Problem Statement
Find all minimum values that must be added at every level in a Binary Tree to make the sum at all levels equal.
Sample Examples
Example 1:
Input:
Output: 7 2 0
Explanation: The sum at every level from the top is (4,9,11) respectively. To make the sum equal at all levels, we must add (7, 2, 0). It will make the final sum (4+7, 9+2, 11+0) or (11, 11, 11).
Example 2:
Input:
Output: 9 6 1 0
Explanation: The sum at every level from the top is (3, 6, 11, 12), respectively. To make the sum equal at every level, we must add (9, 6, 1, 0) to make the final sum (12, 12, 12, 12).
Strategy for Binary Tree problems
Any problem related to either plain binary trees or binary search trees can be solved by combining the use of pointers and recursion. Three things we must very clearly understand every time we approach a binary tree problem are:
- The structure of nodes and pointers making up the tree
- The code manipulating the tree structure
- The recursive algorithm which iterates over the binary tree
Approach
The idea is simple, calculate the sum of all the nodes for every level and store all the level sums in a vector. Find the maximum level sum among all of them. Now, we want to find the minimum value to be added at every Binary tree level to make the sum of all the levels equal. So, the minimum value for the current level = maximum level sum - current level sum.
Steps of algorithm
- Traverse the given Binary tree in level-wise order.
- Create a level_sums vector.
- Calculate the sum of all the nodes for every level and store them in the level_sums vector.
- Calculate the maximum value from the level_sums vector, the maximum level sum in the given Binary tree, and store it in the maxm variable.
- Change the value of every level sum in the level_sums vector to maxm - current level sum.
-
Return the vector.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
vector<int> minimum_value(Node* root)
{
vector<int> level_sums;
if (root == NULL)
return level_sums;
queue<Node*> q;
q.push(root);
int sum = 0;
while (!q.empty())
{
sum = 0;
int size = q.size();
for (int i = 0; i < size; i++)
{
Node* node = q.front();
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
sum += node->data;
}
level_sums.push_back(sum);
}
int maxm = INT_MIN;
for (int i = 0; i < level_sums.size(); i++)
{
maxm = max(maxm, level_sums[i]);
}
for (int i = 0; i < level_sums.size(); i++)
{
level_sums[i] = maxm - level_sums[i];
}
return level_sums;
}
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main()
{
Node* root = newNode(4);
root->left = newNode(3);
root->right = newNode(6);
root->left->left = newNode(3);
root->left->right = newNode(8);
vector<int> ans = minimum_value(root);
for (auto x : ans)
cout << x << " ";
return 0;
}
Output:
7 2 0
Complexity Analysis
Time Complexity: O(N), As we are simply traversing the tree in level-wise order, the time complexity of the above approach is O(N), where N is the number of nodes in the given Binary Tree.
Space Complexity: O(N) where N is the number of nodes in the given Binary tree as we are using a vector to store the level sums.