Minimum Number of Operations to Sort a Binary Tree by Level | Leetcode 2471 | codestorywithMIK

This is the 54th Video of our Playlist "Binary Tree : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve normal Binary Tree problem : Minimum Number of Operations to Sort a Binary Tree by Level | Hidden Problem | Leetcode 2471 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Minimum Number of Operations to Sort a Binary Tree by Level | Hidden Problem | Leetcode 2471 | codestorywithMIK
Company Tags : will update later

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
The solution calculates the minimum number of operations required to sort the values at each level of a binary tree to achieve level-wise sorted order. The approach involves two main steps:

Level-Order Traversal:

Perform a level-order traversal of the binary tree using a queue.
For each level, collect the node values into a list.
Counting Minimum Swaps:

For each level's list, calculate the minimum number of swaps required to sort the list.
Use a hashmap to track the indices of elements for efficient swapping.
Iterate through the list, and whenever an element is out of place, swap it with its correct position, updating the hashmap accordingly.
Increment the swap count for every such operation.

✨ Timelines✨
00:00 - Introduction

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[gamerboy]

Hey bro, I hope you had an incredible trip! I just want to take a moment to thank you for everything you're doing. I currently work at TCS with a very low package, but your support has really motivated and inspired me. I'm feeling super pumped, and I hope to transition to a better company soon. Thanks again for everything, Mik. I truly pray that all your dreams come true.

[dibbodas]

finally after few days mik sir is back✅✅

[ansh]

Finally MIK sir is back ❤️
Sir ho sake to kal wala potd karado copy paste kiya tha kal wala 😅

[gui-codes]

The LEGEND is back 🔥
Waited eagerly to see your videos.

[ravirathore]

I solved it today on my own, thanks for boosting my confidence.

[parulawasthi]

Bhaiya i have been following you for last two months and i could see growth in my problem solving ability. Thankyou so much for providing us with the intuitiveness to solve the questions.
If possible then please cover the leetcode and codechef contests as well.

[Believe_yourself-eoho]

I am done BRUTE FORCE
BFS + Selection Sort Thank you you are back ❤❤❤❤
Please continue DP CONCEPT WALA PLAYLIST 🙏🙏🙏

[shraban]

Finally you are back sir!! Please cover leetcode contests problems!!

[dynamicvk]

Sir, your code of minimum_no_of_swaps function used in this code fails for one testcase in gfg problem: minimum no. of swaps to sort an array at last 1111th test case, could you please tell why it happen because it works correctly for leetcode, It would be very helpful sir

[robot.]

Sir kal ke potd ki ek video solution bana dena.
wo infosys ke interview me poochaa gaya tha

[aws_handles]

MIK is back 😍
Thanks for the clear explanation

[sandeepvishwakarma]

we need yesterday 's solution by you only ❤❤

[dopeCoder]

i did the min swaps with

int minSwaps(vector<int>& vec){
int swaps = 0;
vector<P> arr;
int n = vec.size();

for(int i=0 ; i<n ; i++){
arr.push_back({vec[i], i});
}

sort(begin(arr), end(arr));

for(int i=0 ; i<n ; i++){
P curr = arr[i];
int val = curr.first;
int idx = curr.second;

if(idx != i){
swaps++;
swap(arr[i], arr[idx]);
i--;
}
}
return swaps;
}

[vallendsouza]

Sir, joh 2 din ka upload karna hai voh wale videos kab tak aayenge?

[iamnoob]

Amazing explanation, Is it modified selection sort, If array had duplicates, we may have to go with another approach for finding min swaps.

[VarunSahu-tvrj]

Bhiya codeforces contest ka solution discuss Kiya kro please aap chijo ko acha explain krte hai 🙏

[anonymoushackerar]

MIK Bhaiya, last 2 Days ki POTD ki video kab ayegi? 🥺🥺

[anandpandey]

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/

//Bruteforce approach

class Solution {
private int minimumOperations(TreeNode root) {
int operations = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);

// Perform BFS to get all levels of the tree
while (!queue.isEmpty()) {
int size = queue.size();
int[] level = new int[size];
int index = 0;

for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level[index++] = node.val;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
// For each level, calculate the minimum swaps needed to sort it using selection sort
operations += selectionSortSwaps(level);
}
}

private int selectionSortSwaps(int[] level) {
int swaps = 0;

// Selection Sort with swap counting, using List directly
for (int i = 0; i < level.length - 1; i++) {
// Find the minimum element in the unsorted part of the list
int minIdx = i;
for (int j = i + 1; j < level.length; j++) {
if (level[j] < level[minIdx]) {
minIdx = j;
}
}

// If the minimum element is not already in the correct position, swap
if (minIdx != i) {
swap(level, i, minIdx); // Swap the elements in the arr
swaps++; // Increment swap count
}
}

return swaps;
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}


//Optimal approach

class Solution {
public int minimumOperations(TreeNode root) {
int operations = 0; // To count the total number of swaps required
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root); // Start BFS traversal from the root

while (!queue.isEmpty()) {
int size = queue.size();
int[] level = new int[size]; // Array to store values at the current level
int index = 0;

// Process all nodes at the current level
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll(); // Remove node from the queue
level[index++] = node.val; // Store node value in the array

// Add left and right children to the queue for the next level
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}

// Calculate the minimum swaps required to sort this level
operations += minSwapsToSort(level);
}

return operations; // Return the total number of swaps required
}

private int minSwapsToSort(int[] level) {
// Create a sorted copy of the array
int[] sorted = level.clone();
Arrays.sort(sorted);

// Map each value to its correct index in the sorted array
Map<Integer, Integer> sortedIndexMap = new HashMap<>();
for (int i = 0; i < sorted.length; i++) {
sortedIndexMap.put(sorted[i], i);
}

int swaps = 0;
for (int i = 0; i < level.length;) {
int correctIndex = sortedIndexMap.get(level[i]); // Get the correct index of level[i]
// If the element is already in the correct index, move to the next index
if (i == correctIndex) {
i++;
} else {
// Swap the element to its correct position
swap(level, i, correctIndex);
swaps++; // Increment swap count
}
}
return swaps; // Return the number of swaps required to sort the level
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

[rajashreeparhi]

I am solving questions, working hard..still I am only facing rejections..either my code doesn't run or ques becomes too tricky.... my luck doesn't play well...I am very demotivated.

[princesahu]

bhaiya no of swap dekhne ke liye kyu na ham given array ko sorted array se compare kr le like jis index pe number different honge us samay count++ kar denge and at last count/2 kar denge kyuki jis number se swap hua usme bhi to count++ hoga so is type se number of swap nikal jyega !!