Given a binary tree, the task is to find the minimum number of operations required to make all nodes at the same level have the same value. You can achieve this by performing operations on the nodes, where each operation involves incrementing or decrementing a node’s value by one. Each operation has a cost of 1.
Examples:
Input:
61
/ \
7 2
/ \ / \
6 11 1 3Output: 18
Explanation:
- Level 1 only contains one node so no operations here.
- Level 2 contains two nodes so either 7 can be decremented to 2 or 2 can be incremented to 7, both will cost 5 operations.
- Level 3 contains 4 nodes so all these nodes can be converted to 3 so it will cost a total of 13 operations.
- So total number of operations will be 5 + 13 = 18 operations.
Input:
1
/ \
13 7
/ / \
6 11 4Output: 13
Explaination:
- No operations required for level 1.
- Minimum 6 operations required for level 2 as we can either increment 7 by 6 times or reduce 13 by 6 times.
- Total 7 operations required for level 3 as we can convert all nodes to 6 which will cost total 7 operations.
- So minimum operations required will be 6 + 7 = 13.
Approach: To solve the problem follow the below idea:
For solving this problem, we need to do level order traversal and store the entire level in a vector and if the number of nodes at current level is greater than 1 then calculate the minimum number of operations for making them equal.
Following steps are required for solving this problem :
- Start traversing the tree in level order and store the values of current node in a integer vector.
- If the current level contains more than 1 node then pass the vector after adding all the node’s values to findMin function which will return the minimum number of operations required to make the current level equal.
- Repeat the same for all the levels and add the number of operations for every level in another variable and return it.
- In findMin function, calculate the median of all elements present in the vector and then traverse over the vector and calculate the absolute difference between current element and median value. At last return the sum of all these differences.
Below Code is the implementation of above approach in C++:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Binary tree node struct node { int data; struct node* left; struct node* right; }; // Function for allocating a new node // with the given data and NULL left and right // pointers. struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Function that calculates minimum number // of operations required to make all elements // equal and return the answer int minOperation(vector< int > arr) { sort(arr.begin(), arr.end()); // So the number calculated as median is // the number which will be lead to // minimum operation int median = arr[arr.size() / 2]; // In ans variable calculated the difference // between nodes values and the average int ans = 0; for ( int i = 0; i < arr.size(); i++) { ans += abs (median - arr[i]); } // This ans will be the minimum number of // operations that will be required to // make every element equal return ans; } int findMinOp(node* root) { if (!root) return 0; // Variable for storing the number // of operations int totalOperation = 0; // Queue for level order traversal queue<node*> q; q.push(root); // Level order traversal while (!q.empty()) { // Finding the number of nodes in // current level int n = q.size(); // Vector to store values of // current level nodes vector< int > nodes; // Traversing over the current level for ( int i = 0; i < n; i++) { node* temp = q.front(); q.pop(); if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); nodes.push_back(temp->data); } // If there are more than 1 node in // current level than for making them // equal we will calculate minoperation if (nodes.size() > 1) { // Call the minOperation // function for nodes in // current level and add the // answer to totalOperation totalOperation += minOperation(nodes); } } // After traversing all the levels return // the totalOperation variable return totalOperation; } // Driver code int main() { // Initializing the tree struct node* root = newNode(61); root->left = newNode(7); root->right = newNode(2); root->left->left = newNode(1); root->right->left = newNode(11); root->right->right = newNode(6); root->left->right = newNode(3); // Function call cout << findMinOp(root); return 0; } |
Java
import java.util.*; import java.util.stream.Collectors; import java.util.stream.IntStream; // Binary tree node class Node { int data; Node left, right; // Constructor Node( int data) { this .data = data; left = right = null ; } } public class Main { // Function for calculating minimum number // of operations required to make all elements // equal and return the answer static int minOperation(ArrayList<Integer> arr) { Collections.sort(arr); // The number calculated as the median is // the number that will lead to the // minimum operation int median = arr.get(arr.size() / 2 ); // Initialize the answer variable with 0 int ans = 0 ; for ( int i = 0 ; i < arr.size(); i++) { ans += Math.abs(median - arr.get(i)); } // This 'ans' will be the minimum number of // operations required to make every element equal return ans; } static int findMinOp(Node root) { if (root == null ) return 0 ; // Variable for storing the number // of operations int totalOperation = 0 ; // Queue for level order traversal Queue<Node> q = new LinkedList<>(); q.add(root); // Level order traversal while (!q.isEmpty()) { // Finding the number of nodes in the current level int n = q.size(); // List to store values of current level nodes ArrayList<Integer> nodes = new ArrayList<>(); // Traversing over the current level for ( int i = 0 ; i < n; i++) { Node temp = q.poll(); if (temp.left != null ) q.add(temp.left); if (temp.right != null ) q.add(temp.right); nodes.add(temp.data); } // If there are more than 1 node in the // current level, calculate min operations if (nodes.size() > 1 ) { // Call the minOperation function for nodes in // the current level and add the answer to totalOperation totalOperation += minOperation(nodes); } } // After traversing all the levels, return the totalOperation variable return totalOperation; } // Driver code public static void main(String[] args) { // Initializing the tree Node root = new Node( 61 ); root.left = new Node( 7 ); root.right = new Node( 2 ); root.left.left = new Node( 1 ); root.right.left = new Node( 11 ); root.right.right = new Node( 6 ); root.left.right = new Node( 3 ); // Function call System.out.println(findMinOp(root)); } } |
Python3
# Binary tree node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Function to calculate the minimum number of operations def minOperation(arr): arr.sort() # The median element is the one that minimizes operations median = arr[ len (arr) / / 2 ] # Calculate the total operations total_operation = 0 for element in arr: total_operation + = abs (median - element) return total_operation # Function to find the minimum operations in the binary tree def findMinOp(root): if not root: return 0 # Variable for storing the number of operations total_operation = 0 # Queue for level order traversal queue = [root] # Level order traversal while queue: n = len (queue) nodes = [] # Traversing over the current level for i in range (n): node = queue.pop( 0 ) nodes.append(node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # If there are more than 1 node in the current level # Calculate minOperation for nodes in the current level if len (nodes) > 1 : total_operation + = minOperation(nodes) return total_operation # Driver code if __name__ = = "__main__" : # Initializing the tree root = Node( 61 ) root.left = Node( 7 ) root.right = Node( 2 ) root.left.left = Node( 1 ) root.right.left = Node( 11 ) root.right.right = Node( 6 ) root.left.right = Node( 3 ) # Function call print (findMinOp(root)) #Contributed by Aditi Tyagi |
C#
// C# code for the above approach: using System; using System.Collections.Generic; using System.Linq; // Binary tree node class Node { public int data; public Node left, right; // Constructor public Node( int data) { this .data = data; left = right = null ; } } public class GFG { // Function for calculating minimum number // of operations required to make all elements // equal and return the answer static int MinOperation(List< int > arr) { arr.Sort(); // The number calculated as the median is // the number that will lead to the // minimum operation int median = arr[arr.Count / 2]; // Initialize the answer variable with 0 int ans = 0; foreach ( int num in arr) { ans += Math.Abs(median - num); } // This 'ans' will be the minimum number of // operations required to make every element equal return ans; } static int FindMinOp(Node root) { if (root == null ) return 0; // Variable for storing the number // of operations int totalOperation = 0; // Queue for level order traversal Queue<Node> q = new Queue<Node>(); q.Enqueue(root); // Level order traversal while (q.Count > 0) { // Finding the number of nodes in the current level int n = q.Count; // List to store values of current level nodes List< int > nodes = new List< int >(); // Traversing over the current level for ( int i = 0; i < n; i++) { Node temp = q.Dequeue(); if (temp.left != null ) q.Enqueue(temp.left); if (temp.right != null ) q.Enqueue(temp.right); nodes.Add(temp.data); } // If there are more than 1 node in the // current level, calculate min operations if (nodes.Count > 1) { // Call the MinOperation function for nodes in // the current level and add the answer to totalOperation totalOperation += MinOperation(nodes); } } // After traversing all the levels, return the totalOperation variable return totalOperation; } // Driver code public static void Main( string [] args) { // Initializing the tree Node root = new Node(61); root.left = new Node(7); root.right = new Node(2); root.left.left = new Node(1); root.right.left = new Node(11); root.right.right = new Node(6); root.left.right = new Node(3); // Function call Console.WriteLine(FindMinOp(root)); } } |
Javascript
// JavaScript code for the above approach: // Binary tree node class TreeNode { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Function that calculates minimum number // of operations required to make all elements // equal and returns the answer function minOperation(arr) { arr.sort((a, b) => a - b); // The number calculated as the median is // the number which will lead to // the minimum operation const median = arr[Math.floor(arr.length / 2)]; // Initialize ans variable to store the difference // between node values and the average let ans = 0; for (let i = 0; i < arr.length; i++) { ans += Math.abs(median - arr[i]); } // This ans will be the minimum number of // operations required to make every element equal return ans; } function findMinOp(root) { if (!root) { return 0; } // Variable for storing the number // of operations let totalOperation = 0; // Queue for level order traversal const queue = []; queue.push(root); // Level order traversal while (queue.length > 0) { // Finding the number of nodes in // the current level const n = queue.length; // Array to store values of // current level nodes const nodes = []; // Traversing over the current level for (let i = 0; i < n; i++) { const temp = queue.shift(); if (temp.left !== null ) { queue.push(temp.left); } if (temp.right !== null ) { queue.push(temp.right); } nodes.push(temp.data); } // If there are more than 1 node in // the current level, calculate minoperation if (nodes.length > 1) { // Call the minOperation // function for nodes in // the current level and add the // answer to totalOperation totalOperation += minOperation(nodes); } } // After traversing all the levels, return // the totalOperation variable return totalOperation; } // Driver code // Initializing the tree const root = new TreeNode(61); root.left = new TreeNode(7); root.right = new TreeNode(2); root.left.left = new TreeNode(1); root.right.left = new TreeNode(11); root.right.right = new TreeNode(6); root.left.right = new TreeNode(3); // Function call console.log(findMinOp(root)); |
18
Time Complexity: O(N*LogN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!