Table of contents
1.
Introduction
1.1.
Problem Statement
1.1.1.
Sample Examples
1.2.
Strategy for Binary Tree problems
2.
Approach
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the use of a Binary Tree?
3.2.
Is level order traversal equivalent to BFS?
3.3.
Can a binary tree have only one child?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Minimum Value to be Added at every Binary Tree Level to make the Sum at all Levels Equal

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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.

Frequently Asked Questions

What is the use of a Binary Tree?

Binary trees are primarily used and preferred to search and sort because they easily store data hierarchically. Binary trees usually involve operations such as transversal, insertion and deletion.

Is level order traversal equivalent to BFS?

Yes, Level Order Traversal is also known as Breadth-First Traversal as it traverses all nodes at each level before proceeding to the next (depth).

Can a binary tree have only one child?

Yes, a binary tree is a tree in which no node has more than two children, and every child is either a left or a right child, even if it is the parent's only child.

Conclusion

In this article, we learned the basics about binary trees and solved the specific problem of calculating the minimum number to be added at every level in a binary tree to make the sum at all levels equal to its C++ code.

We hope that this blog has helped you enhance your knowledge regarding Binary Tree, and if you would like to practice more, you can go to Coding Ninjas Studio to try and solve more problems.

Recommended Reading: 

 

Recommended problems -

 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Live masterclass