✅ Easy to Understand | BFS | Java | C++ | Python | Detailed Video Explanation 🔥
IntuitionThe problem requires determining the minimum number of operations to sort each level of a binary tree when traversed level by level. My first thought w
# Intuition
The problem requires determining the minimum number of operations to sort each level of a binary tree when traversed level by level. My first thought was to utilize level-order traversal to access the nodes level-wise and then determine how many swaps are needed to sort the node values at each level. The count of swaps gives the required number of operations for that level, and the sum of these counts for all levels is the answer.

# Approach
1. Perform a level-order traversal using a queue to process nodes level by level.
2. For each level:
   - Extract all node values into a list.
   - Determine the number of swaps required to sort the list using the `countSwaps` function.
3. In the `countSwaps` function:
   - Use a hashmap to track the current positions of the elements.
   - Compare the current list with its sorted version. If an element is out of place, swap it with the correct element and update the hashmap.
4. Accumulate the total number of swaps for all levels.
5. Return the accumulated result as the final answer.

# Complexity
- Time complexity:
  - Level-order traversal: $$O(n)$$, where $$n$$ is the total number of nodes in the tree.
  - Sorting and counting swaps for each level:
    - Sorting: $$O(k \log k)$$ for a level with $$k$$ nodes.
    - Counting swaps: $$O(k)$$ for a level with $$k$$ nodes (amortized with hashmap).
    - Total across all levels: $$O(n \log k)$$, where $$k$$ is the maximum width of the tree.
  - Overall: $$O(n \log k)$$.

- Space complexity:
  - Queue for level-order traversal: $$O(k)$$, where $$k$$ is the maximum width of the tree.
  - Additional storage for lists and maps at each level: $$O(k)$$.
  - Overall: $$O(k)$$.


# Code
```java []
/**
 * 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;
 *     }
 * }
 */

class Solution {

    /**
     * Calculates the minimum number of operations required to sort each level
     * of a binary tree when traversed level by level.
     * @param root The root node of the binary tree.
     * @return The minimum number of operations.
     */
    public int minimumOperations(TreeNode root) {
        if (root == null) return 0; // Base case: empty tree requires no operations.
        int ans = 0; // Total number of swaps required.

        // Queue for level order traversal.
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root); // Start with the root node.
        int levelNo = 0; // Track the level number (optional).

        // Perform level order traversal.
        while (!q.isEmpty()) {
            int len = q.size(); // Number of nodes at the current level.
            List<Integer> level = new ArrayList<>(); // List to store values at the current level.

            // Traverse all nodes at the current level.
            while (len-- > 0) {
                TreeNode node = q.poll(); // Remove the front node from the queue.
                level.add(node.val); // Add the node's value to the level list.

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

            // Count the number of swaps required to sort the current level.
            ans += countSwaps(level);

            // Finished processing this level.
            levelNo++;
        }

        return ans; // Return the total number of swaps.
    }

    /**
     * Calculates the minimum number of swaps required to sort a list of integers.
     * @param level The list of integers representing the values at a tree level.
     * @return The number of swaps required to sort the list.
     */
    public static int countSwaps(List<Integer> level) {
        int n = level.size();
        int swaps = 0;

        // Create a sorted version of the list.
        List<Integer> sortedLevel = new ArrayList<>(level);
        Collections.sort(sortedLevel);

        // Map to store the indices of elements in the current list.
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(level.get(i), i);
        }

        // Iterate through the list to identify misplaced elements.
        for (int i = 0; i < n; i++) {
            // If the current element is not in its sorted position.
            if (!level.get(i).equals(sortedLevel.get(i))) {
                // Find the correct index of the current element.
                int correctIndex = indexMap.get(sortedLevel.get(i));

                // Update the map to reflect the swap.
                indexMap.put(level.get(i), correctIndex);
                indexMap.put(level.get(correctIndex), i);

                // Swap the elements to place them correctly.
                Collections.swap(level, i, correctIndex);
                swaps++; // Increment the swap count.
            }
        }

        return swaps; // Return the total number of swaps.
    }

    /**
     * An alternative method to calculate the number of swaps required to sort a list of integers.
     * This method uses O(N^2) time complexity and may result in TLE (Time Limit Exceeded).
     * @param level The list of integers representing the values at a tree level.
     * @return The number of swaps required to sort the list.
     */
    public static int countSwapsN2(List<Integer> level) {
        int n = level.size();
        int swaps = 0;

        // Create a sorted version of the list.
        List<Integer> sortedLevel = new ArrayList<>(level);
        Collections.sort(sortedLevel);

        // Iterate through the list to identify misplaced elements.
        for (int i = 0; i < n; i++) {
            // If the current element is not in its sorted position.
            if (!level.get(i).equals(sortedLevel.get(i))) {
                // Find the correct index of the current element.
                int correctIndex = level.indexOf(sortedLevel.get(i));

                // Swap the elements to place them correctly.
                Collections.swap(level, i, correctIndex);
                swaps++; // Increment the swap count.
            }
        }
        return swaps; // Return the total number of swaps.
    }
}

```
```C++ []
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        if (!root) return 0;
        int ans = 0;

        queue<TreeNode*> q;
        q.push(root);

        // Perform level order traversal.
        while (!q.empty()) {
            int len = q.size();
            vector<int> level;

            // Traverse nodes at the current level.
            for (int i = 0; i < len; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            // Count swaps needed to sort this level.
            ans += countSwaps(level);
        }

        return ans;
    }

private:
    int countSwaps(vector<int>& level) {
        int n = level.size();
        vector<int> sortedLevel(level);
        sort(sortedLevel.begin(), sortedLevel.end());
        unordered_map<int, int> indexMap;

        for (int i = 0; i < n; ++i) {
            indexMap[level[i]] = i;
        }

        int swaps = 0;
        for (int i = 0; i < n; ++i) {
            if (level[i] != sortedLevel[i]) {
                int correctIndex = indexMap[sortedLevel[i]];

                // Update the index map for the swapped elements.
                indexMap[level[i]] = correctIndex;
                indexMap[level[correctIndex]] = i;

                // Swap elements.
                swap(level[i], level[correctIndex]);
                swaps++;
            }
        }

        return swaps;
    }
};

```
```python []
from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minimumOperations(self, root: TreeNode) -> int:
        if not root:
            return 0
        ans = 0

        # Perform level-order traversal
        q = deque([root])

        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            # Count swaps needed to sort this level
            ans += self.countSwaps(level)

        return ans

    def countSwaps(self, level):
        n = len(level)
        sorted_level = sorted(level)
        index_map = {val: i for i, val in enumerate(level)}
        swaps = 0

        for i in range(n):
            while level[i] != sorted_level[i]:
                correct_index = index_map[sorted_level[i]]

                # Update the index map before swapping
                index_map[level[i]] = correct_index
                index_map[level[correct_index]] = i

                # Swap elements
                level[i], level[correct_index] = level[correct_index], level[i]
                swaps += 1

        return swaps

```


LeetCode 2471 Minimum Number of Operations to Sort a Binary Tree by Level | Tree | Asked in Amazon
https://youtu.be/wVZAZ-NBqQI
['Tree', 'Breadth-First Search', 'Binary Tree', 'Python', 'C++', 'Java']