Minimum operations required to make every node at same level equal - Coding

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 3

Output: 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 4

Output: 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));

Output

Time Complexity: O(N*LogN)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

DSA

Related
Split Array into Consecutive Subsequences of Size K or more.
Maximum Square Side length with M 1x1 and N 2x2 tiles
Number of K-Spikes in Stock Price Array
Exploring Range Trees
Count the participants defeating maximum individuals in a competition

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12