Horje
minimum operation to make every leaf node equal

Given a binary tree that contains multiple nodes, the task is to find a minimum number of operations required to make leaf nodes at the same level equal. By performing one operation you can either increase the node’s value by one or decrease the node’s value by one.

Examples:

Input:

6
/ \
4 2
/ \ / \
1 9 5 3
/
10

Output: 6
Explanation: There is no leaf node at levels 1 and 2, we have 3 leaf nodes at level 3 which have values 9, 5, and 3. To make these three equal we can reduce 9 by 4 which will cost 4 operations then second leaf node 5 will remain the same and then the third leaf node will be incremented twice which will cost 2 operations. So in the end all leaf nodes at level three will have a value of 5 and this will cost a total of 6 operations. At level 4 there is only 1 leaf node so no operations will be performed here.

Input:

4
/ \
5 7

Output: 2
Explaination: There are two leaf nodes at level 2 which have values 5 and 7 so we can increment 5 by 2 and this will cost us 2 operations .2 is the minimum number of operations required to make leaf nodes at level 2 equal.

Approach: To solve the problem follow the below idea:

The idea is to find the total number of nodes which we need to make equal in the same level then after finding these nodes calculate minimum number of operations by making each element equal to average of all elements.

Follow the steps to solve the problem:

  • Start traversing the tree in level order and for every level check whether the current node is leaf or not if Yes then insert the current node’s value in a integer vector and once completing entire level pass the vector to another function which will calculate the minimum number of operation required ,for calculating the minimum number of operations do the below mentioned steps :
  • Find the average of all elements present in leaf vector.
  • Then traverse over the vector and find absolute difference between current element and average value and return this sum of absolute differences
  • and then do the same for remaining value and add the total received by this function for multiple levels and return the sum .

Below code is implementation for above approach in C++:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node has data,
// left child and right child
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// Helper function that allocates 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 returns true if current node
// is leaf otherwise false
bool isLeaf(node* root)
{
    if (root->left == NULL && root->right == NULL)
        return true;
    return false;
}
 
// Function that calculates minimum number
// of operations required to make all elements
// of array equal and return that value
int findMinOperation(vector<int> leafs)
{
    int val = leafs[0];
 
    // Running for loop for calculating the
    // average of all numbers present in array
    for (int i = 1; i < leafs.size(); i++) {
        val = (val + leafs[i]) / 2;
    }
 
    // So the number calculated as average is
    // the number which will be lead to
    // minimum operation
    int ans
        = 0; // In ans variable calculated the difference
             // between leaf's values and the average
    for (int i = 0; i < leafs.size(); i++) {
        ans += abs(val - leafs[i]);
    }
 
    // This ans will be the minimum number of
    // operations which will be required to
    // make every element equal
    return ans;
}
 
int minimumOperation(node* root)
{
    if (!root)
        return 0;
 
    // Variable for storing the number
    // of operations
    int minOperation = 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 which maintains the track of
        // leaf nodes in current level
        vector<int> leafs;
 
        // 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);
 
            // If current node is a leaf
            // node then push its value in
            // leafs vector
            if (isLeaf(temp))
                leafs.push_back(temp->data);
        }
 
        // If there are more than 1 leaf node in
        // current level than for making them
        // equal we will calculate minoperation
        if (leafs.size() > 1) {
 
            // Call the findMinOperation
            // function for leaf nodes in
            // current level and add the answer
            // to minOperation
            minOperation += findMinOperation(leafs);
        }
    }
 
    // After traversing all the levels return
    // the minOperation variable
    return minOperation;
}
 
// Driver code
int main()
{
 
    // Initializing the tree
    struct node* root = newNode(6);
    root->left = newNode(4);
    root->right = newNode(2);
    root->left->left = newNode(1);
    root->left->right = newNode(9);
    root->right->left = newNode(5);
    root->right->right = newNode(3);
    root->left->left->right = newNode(10);
 
    // Function call
    cout << minimumOperation(root);
 
    return 0;
}

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;
 
// A binary tree node has data,
// left child, and right child
class Node {
    int data;
    Node left;
    Node right;
 
    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}
 
public class Main {
    // Function that returns true if the current node
    // is a leaf, otherwise false
    static boolean isLeaf(Node root) {
        return root.left == null && root.right == null;
    }
 
    // Function that calculates the minimum number
    // of operations required to make all elements
    // of the array equal and return that value
    static int findMinOperation(Vector<Integer> leafs) {
        int val = leafs.get(0);
 
        // Running a for loop for calculating the
        // average of all numbers present in the array
        for (int i = 1; i < leafs.size(); i++) {
            val = (val + leafs.get(i)) / 2;
        }
 
        // The number calculated as the average is
        // the number which will lead to
        // the minimum operation
        int ans = 0; // In the ans variable, calculate the difference
                     // between leaf's values and the average
        for (int i = 0; i < leafs.size(); i++) {
            ans += Math.abs(val - leafs.get(i));
        }
 
        // This ans will be the minimum number of
        // operations required to make every element equal
        return ans;
    }
 
    static int minimumOperation(Node root) {
        if (root == null)
            return 0;
 
        // Variable for storing the number
        // of operations
        int minOperation = 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();
 
            // Vector that maintains the track of
            // leaf nodes in the current level
            Vector<Integer> leafs = new Vector<>();
 
            // 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);
 
                // If the current node is a leaf
                // node, then add its value to
                // the leafs vector
                if (isLeaf(temp))
                    leafs.add(temp.data);
            }
 
            // If there are more than 1 leaf nodes in
            // the current level, then for making them
            // equal, we will calculate minOperation
            if (leafs.size() > 1) {
 
                // Call the findMinOperation
                // function for leaf nodes in
                // the current level and add the answer
                // to minOperation
                minOperation += findMinOperation(leafs);
            }
        }
 
        // After traversing all the levels, return
        // the minOperation variable
        return minOperation;
    }
 
    // Driver code
    public static void main(String[] args) {
        // Initializing the tree
        Node root = new Node(6);
        root.left = new Node(4);
        root.right = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(9);
        root.right.left = new Node(5);
        root.right.right = new Node(3);
        root.left.left.right = new Node(10);
 
        // Function call
        System.out.println(minimumOperation(root));
    }
}

Python3

from queue import Queue
 
# A binary tree node has data,
# left child, and right child
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function that returns true if current node
# is leaf, otherwise false
def isLeaf(root):
    if root.left is None and root.right is None:
        return True
    return False
 
# Function that calculates minimum number
# of operations required to make all elements
# of array equal and return that value
def findMinOperation(leafs):
    val = leafs[0]
 
    # Running for loop for calculating the
    # average of all numbers present in the array
    for i in range(1, len(leafs)):
        val = (val + leafs[i]) // 2
 
    # So the number calculated as the average is
    # the number which will lead to minimum operations
    ans = 0  # In ans variable calculated the difference
             # between leaf's values and the average
    for i in range(len(leafs)):
        ans += abs(val - leafs[i])
 
    # This ans will be the minimum number of
    # operations required to make every element equal
    return ans
 
def minimumOperation(root):
    if not root:
        return 0
 
    # Variable for storing the number
    # of operations
    minOperation = 0
 
    # Queue for level-order traversal
    q = Queue()
    q.put(root)
 
    # Level-order traversal
    while not q.empty():
 
        # Finding the number of nodes in
        # the current level
        n = q.qsize()
 
        # List which maintains the track of
        # leaf nodes in the current level
        leafs = []
 
        # Traversing over the current level
        for i in range(n):
            temp = q.get()
            if temp.left is not None:
                q.put(temp.left)
            if temp.right is not None:
                q.put(temp.right)
 
            # If the current node is a leaf
            # node then append its value in
            # the leafs list
            if isLeaf(temp):
                leafs.append(temp.data)
 
        # If there are more than 1 leaf node in
        # the current level then for making them
        # equal, we will calculate minOperation
        if len(leafs) > 1:
 
            # Call the findMinOperation
            # function for leaf nodes in
            # the current level and add the answer
            # to minOperation
            minOperation += findMinOperation(leafs)
 
    # After traversing all the levels, return
    # the minOperation variable
    return minOperation
 
# Driver code
if __name__ == "__main__":
    # Initializing the tree
    root = Node(6)
    root.left = Node(4)
    root.right = Node(2)
    root.left.left = Node(1)
    root.left.right = Node(9)
    root.right.left = Node(5)
    root.right.right = Node(3)
    root.left.left.right = Node(10)
 
    # Function call
    print(minimumOperation(root))
#This Code is Contributed by chinmaya121221

C#

using System;
using System.Collections.Generic;
 
// A binary tree node has data,
// left child and right child
public class Node
{
    public int Data;
    public Node Left;
    public Node Right;
 
    public Node(int data)
    {
        Data = data;
        Left = null;
        Right = null;
    }
}
 
class Program
{
    // Function that returns true if current node
    // is leaf, otherwise false
    static bool IsLeaf(Node root)
    {
        return (root.Left == null && root.Right == null);
    }
 
    // Function that calculates the minimum number
    // of operations required to make all elements
    // of an array equal and returns that value
    static int FindMinOperation(List<int> leafs)
    {
        int val = leafs[0];
 
        // Running for loop for calculating the
        // average of all numbers present in the array
        for (int i = 1; i < leafs.Count; i++)
        {
            val = (val + leafs[i]) / 2;
        }
 
        // So the number calculated as average is
        // the number which will lead to
        // the minimum operation
        int ans = 0; // In ans variable, calculate the difference
                     // between leaf values and the average
 
        foreach (int leaf in leafs)
        {
            ans += Math.Abs(val - leaf);
        }
 
        // This ans will be the minimum number of
        // operations required to make every element equal
        return ans;
    }
 
    static int MinimumOperation(Node root)
    {
        if (root == null)
            return 0;
 
        // Variable for storing the number of operations
        int minOperation = 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 which maintains the track of leaf nodes in the current level
            List<int> leafs = 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);
 
                // If the current node is a leaf node, then add its value to the leafs list
                if (IsLeaf(temp))
                    leafs.Add(temp.Data);
            }
 
            // If there are more than 1 leaf node in
            // the current level, then for making them
            // equal, calculate minOperation
            if (leafs.Count > 1)
            {
                // Call the FindMinOperation function for leaf nodes in
                // the current level and add the answer to minOperation
                minOperation += FindMinOperation(leafs);
            }
        }
 
        // After traversing all the levels, return
        // the minOperation variable
        return minOperation;
    }
 
    // Driver code
    static void Main()
    {
        // Initializing the tree
        Node root = new Node(6);
        root.Left = new Node(4);
        root.Right = new Node(2);
        root.Left.Left = new Node(1);
        root.Left.Right = new Node(9);
        root.Right.Left = new Node(5);
        root.Right.Right = new Node(3);
        root.Left.Left.Right = new Node(10);
 
        // Function call
        Console.WriteLine(MinimumOperation(root));
    }
}

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
function isLeaf(root) {
    return !root.left && !root.right;
}
 
function findMinOperation(leafs) {
    let val = leafs[0];
 
    for (let i = 1; i < leafs.length; i++) {
        val = (val + leafs[i]) / 2;
    }
 
    let ans = 0;
 
    for (let i = 0; i < leafs.length; i++) {
        ans += Math.abs(val - leafs[i]);
    }
 
    return ans;
}
 
function minimumOperation(root) {
    if (!root) {
        return 0;
    }
 
    let minOperation = 0;
    const queue = [root];
 
    while (queue.length > 0) {
        const n = queue.length;
        const leafs = [];
 
        for (let i = 0; i < n; i++) {
            const temp = queue.shift();
 
            if (temp.left) {
                queue.push(temp.left);
            }
 
            if (temp.right) {
                queue.push(temp.right);
            }
 
            if (isLeaf(temp)) {
                leafs.push(temp.data);
            }
        }
 
        if (leafs.length > 1) {
            minOperation += findMinOperation(leafs);
        }
    }
 
    return minOperation;
}
 
// Driver code
const root = new Node(6);
root.left = new Node(4);
root.right = new Node(2);
root.left.left = new Node(1);
root.left.right = new Node(9);
root.right.left = new Node(5);
root.right.right = new Node(3);
root.left.left.right = new Node(10);
 
console.log(minimumOperation(root));

Output

6

Time Complexity: O(N), traversing over the tree
Auxillary space: O(N), because of queue used


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Print a singly linked list in spiral order Print a singly linked list in spiral order
Find the Root of a Tree Find the Root of a Tree
Accessing characters by index in a String Accessing characters by index in a String
Minimum swaps required in the String such that S[i] != S[n-i+1] Minimum swaps required in the String such that S[i] != S[n-i+1]
Count the unique type of nodes present in Binary tree Count the unique type of nodes present in Binary tree

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



 

Horje