Given a binary tree, the task is to find all minimum values greater than or equal to zero, that should be added at each level to make the sum at each level equal.
Examples:
Input:
1
/ \
2 3
/ \
4 5
Output: 8 4 0
Explanation: Initial sum at each level is {1, 5, 9}. To make all levels sum equal minimum values to be added are {8, 4, 0}. So the final sums at each level becomes {1 + 8, 5 + 4, 9 + 0} i.e. {9, 9, 9}.Input:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Output: 16 11 3 0
Approach: The given problem can be solved by finding the maximum level sum in a binary tree. By the greedy approach, the minimum value that should be added at each level must be equal to the difference between the sum of that level in the binary tree with the maximum level sum in a binary tree.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Node classclass Node {public: int data; Node *left, *right; Node(int item) { data = item; left = right = NULL; }};// Function to find sum of nodes// present in a single level.void Utilfun(Node* root, int level, vector<int>& ans){ if (root == NULL) { return; } // Adding the data // of all the level if (ans.size() == level) { ans.push_back(root->data); } // If previous node data is already // then update ans else { int val = ans[level] + root->data; ans[level] = val; } // Basic dfs approach to traverse // on all the nodes with next level Utilfun(root->left, level + 1, ans); Utilfun(root->right, level + 1, ans);}// Function to find the minimum// value added to make each level// sum equalvector<int>levelOrderAP(Node* root){ // Initialization of array vector<int> finalAns; // If root is null if (root == NULL) { return finalAns; } // Function Call Utilfun(root, 0, finalAns); int maxi = INT_MIN; // finding the maximum element for (int ele : finalAns) { maxi = max(maxi, ele); } // Subtracting all the elements // from maximum elements for (int i = 0; i < finalAns.size(); i++) { int val = maxi - finalAns[i]; finalAns[i] = val; } return finalAns;}// Driver Codeint main(){ Node* root = new Node(8); root->left = new Node(3); root->right = new Node(10); root->left->left = new Node(1); root->left->right = new Node(6); root->right->right = new Node(14); root->left->right->left = new Node(4); root->left->right->right = new Node(7); root->right->right->left = new Node(13); vector<int> ans = levelOrderAP(root); for (auto i : ans) { cout << i << " "; } return 0;}// This code is contributed by maddler. |
Java
// Java program for the above approachimport java.util.*;// Node classclass Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; }}// Binary tree classclass BinaryTree { Node root; public BinaryTree() { root = null; } // Function to find the minimum // value added to make each level // sum equal static ArrayList<Integer> levelOrderAP(Node root) { // Initialization of array ArrayList<Integer> finalAns = new ArrayList<>(); // If root is null if (root == null) { return finalAns; } // Function Call Utilfun(root, 0, finalAns); int maxi = Integer.MIN_VALUE; // finding the maximum element for (int ele : finalAns) { maxi = Math.max(maxi, ele); } // Subtracting all the elements // from maximum elements for (int i = 0; i < finalAns.size(); i++) { int val = maxi - finalAns.get(i); finalAns.set(i, val); } return finalAns; } // Function to find sum of nodes // present in a single level. static void Utilfun(Node root, int level, ArrayList<Integer> ans) { if (root == null) { return; } // Adding the data // of all the level if (ans.size() == level) { ans.add(root.data); } // If previous node data is already // then update ans else { int val = ans.get(level) + root.data; ans.set(level, val); } // Basic dfs approach to traverse // on all the nodes with next level Utilfun(root.left, level + 1, ans); Utilfun(root.right, level + 1, ans); } // Driver Code public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(8); tree.root.left = new Node(3); tree.root.right = new Node(10); tree.root.left.left = new Node(1); tree.root.left.right = new Node(6); tree.root.right.right = new Node(14); tree.root.left.right.left = new Node(4); tree.root.left.right.right = new Node(7); tree.root.right.right.left = new Node(13); ArrayList<Integer> ans = levelOrderAP(tree.root); System.out.println(ans); }} |
Python3
# Python3 program for the above approachimport sys# Structure of Nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = Nonedef newNode(data): temp = Node(data) return temp # Function to find the minimum# value added to make each level# sum equaldef levelOrderAP(root): # Initialization of array finalAns = [] # If root is null if (root == None): return finalAns # Function Call Utilfun(root, 0, finalAns) maxi = -sys.maxsize # finding the maximum element for ele in range(len(finalAns)): maxi = max(maxi, finalAns[ele]) # Subtracting all the elements # from maximum elements for i in range(len(finalAns)): val = maxi - finalAns[i] finalAns[i] = val return finalAns# Function to find sum of nodes# present in a single level.def Utilfun(root, level, ans): if (root == None): return # Adding the data # of all the level if (len(ans) == level): ans.append(root.data) # If previous node data is already # then update ans else: val = ans[level] + root.data ans[level] = val # Basic dfs approach to traverse # on all the nodes with next level Utilfun(root.left, level + 1, ans) Utilfun(root.right, level + 1, ans)root = newNode(8)root.left = newNode(3)root.right = newNode(10)root.left.left = newNode(1)root.left.right = newNode(6)root.right.right = newNode(14)root.left.right.left = newNode(4)root.left.right.right = newNode(7)root.right.right.left = newNode(13)ans = levelOrderAP(root)print("[", end="")for i in range(len(ans) - 1): print(ans[i], ", ", sep = "", end = "")print(ans[-1], "]", sep = "")# This code is contributed by rameshtravel07. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{public class Node{ public int data; public Node left, right;};static Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;} // Function to find the minimum // value added to make each level // sum equal static List<int> levelOrderAP(Node root) { // Initialization of array List<int> finalAns = new List<int>(); // If root is null if (root == null) { return finalAns; } // Function Call Utilfun(root, 0, finalAns); int maxi = Int32.MinValue; // finding the maximum element foreach (int ele in finalAns) { maxi = Math.Max(maxi, ele); } // Subtracting all the elements // from maximum elements for (int i = 0; i < finalAns.Count; i++) { int val = maxi - finalAns[i]; finalAns[i] = val; } return finalAns; } // Function to find sum of nodes // present in a single level. static void Utilfun(Node root, int level, List<int> ans) { if (root == null) { return; } // Adding the data // of all the level if (ans.Count == level) { ans.Add(root.data); } // If previous node data is already // then update ans else { int val = ans[level] + root.data; ans[level] = val; } // Basic dfs approach to traverse // on all the nodes with next level Utilfun(root.left, level + 1, ans); Utilfun(root.right, level + 1, ans); } // Driver Code public static void Main() { Node root = newNode(8); root.left = newNode(3); root.right = newNode(10); root.left.left = newNode(1); root.left.right = newNode(6); root.right.right = newNode(14); root.left.right.left = newNode(4); root.left.right.right = newNode(7); root.right.right.left = newNode(13); List<int> ans = levelOrderAP(root); foreach(int i in ans) Console.Write(i+ " "); }}// This code is contributed by ipg2016107. |
Javascript
<script> // Javascript program for the above approach class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } function newNode(data) { let temp = new Node(data); return temp; } // Function to find the minimum // value added to make each level // sum equal function levelOrderAP(root) { // Initialization of array let finalAns = []; // If root is null if (root == null) { return finalAns; } // Function Call Utilfun(root, 0, finalAns); let maxi = Number.MIN_VALUE; // finding the maximum element for(let ele = 0; ele < finalAns.length; ele++) { maxi = Math.max(maxi, finalAns[ele]); } // Subtracting all the elements // from maximum elements for (let i = 0; i < finalAns.length; i++) { let val = maxi - finalAns[i]; finalAns[i] = val; } return finalAns; } // Function to find sum of nodes // present in a single level. function Utilfun(root, level, ans) { if (root == null) { return; } // Adding the data // of all the level if (ans.length == level) { ans.push(root.data); } // If previous node data is already // then update ans else { let val = ans[level] + root.data; ans[level] = val; } // Basic dfs approach to traverse // on all the nodes with next level Utilfun(root.left, level + 1, ans); Utilfun(root.right, level + 1, ans); } let root = newNode(8); root.left = newNode(3); root.right = newNode(10); root.left.left = newNode(1); root.left.right = newNode(6); root.right.right = newNode(14); root.left.right.left = newNode(4); root.left.right.right = newNode(7); root.right.right.left = newNode(13); let ans = levelOrderAP(root); document.write("["); for(let i = 0; i < ans.length - 1; i++) { document.write(ans[i] + ", "); } document.write(ans[ans.length - 1] + "]");// This code is contributed by decode2207.</script> |
Output
[16, 11, 3, 0]
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
