🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
IntuitionThis problem involves minimizing operations to sort the values of a binary tree level by level. The key idea is to treat each level of the binary tree
### Intuition
This problem involves minimizing operations to sort the values of a binary tree level by level. The key idea is to treat each level of the binary tree as a separate array and calculate the minimum number of swaps required to sort that array. By using breadth-first traversal, we can process the tree level by level and solve the sorting problem for each level.

---

### Approach
1. **Level-order Traversal**:
   - Use a queue to perform a breadth-first traversal of the binary tree.
   - For each level, store the values of the nodes in an array.

2. **Sorting with Minimum Swaps**:
   - For each level, compute the number of swaps required to sort the array of values. This is done by:
     - Creating a sorted version of the array.
     - Using a mapping to track indices in the original array.
     - Simulating swaps and counting them until the array becomes sorted.

3. **Summing Results**:
   - Accumulate the swap counts for all levels to get the final result.

---

### Complexity
- **Time Complexity**:
  - Level-order traversal: $$O(n)$$, where $$n$$ is the number of nodes in the tree.
  - Sorting for each level: $$O(k \log k)$$, where $$k$$ is the number of nodes in the current level. Across all levels, this sums to $$O(n \log n)$$.
  - Mapping and swapping: $$O(k)$$ per level, or $$O(n)$$ overall.
  - **Total**: $$O(n \log n)$$.

- **Space Complexity**:
  - Storage for level arrays: $$O(k)$$, where $$k$$ is the maximum number of nodes in any level.
  - Mapping and auxiliary space for sorting: $$O(k)$$.
  - Queue for traversal: $$O(n)$$ in the worst case.
  - **Total**: $$O(n)$$.

---


```python []
from collections import deque

class Solution:
    def minimumOperations(self, root):
        def count_swaps(arr):
            n = len(arr)
            sorted_arr = sorted(arr)
            index_map = {value: i for i, value in enumerate(arr)}
            swaps = 0
            for i in range(n):
                while arr[i] != sorted_arr[i]:
                    swaps += 1
                    target_index = index_map[sorted_arr[i]]
                    arr[i], arr[target_index] = arr[target_index], arr[i]
                    index_map[arr[target_index]] = target_index
                    index_map[arr[i]] = i
            return swaps

        count = 0
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            count += count_swaps(level)
        return count
```
```dart []
class TreeNode {
  int val;
  TreeNode? left;
  TreeNode? right;
  TreeNode(this.val, [this.left, this.right]);
}

class Solution {
  int minimumOperations(TreeNode root) {
    int count = 0;
    Queue<TreeNode> queue = Queue<TreeNode>();
    queue.add(root);

    while (queue.isNotEmpty) {
      List<int> level = [];
      for (int i = 0, size = queue.length; i < size; i++) {
        TreeNode node = queue.removeFirst();
        level.add(node.val);
        if (node.left != null) queue.add(node.left!);
        if (node.right != null) queue.add(node.right!);
      }
      count += _countSwaps(level);
    }
    return count;
  }

  int _countSwaps(List<int> arr) {
    List<int> sortedArr = List.from(arr)..sort();
    Map<int, int> indexMap = {
      for (int i = 0; i < arr.length; i++) arr[i]: i
    };
    int swaps = 0;

    for (int i = 0; i < arr.length; i++) {
      while (arr[i] != sortedArr[i]) {
        swaps++;
        int targetIndex = indexMap[sortedArr[i]]!;
        int temp = arr[i];
        arr[i] = arr[targetIndex];
        arr[targetIndex] = temp;
        indexMap[arr[targetIndex]] = targetIndex;
        indexMap[arr[i]] = i;
      }
    }
    return swaps;
  }
}
```
```javascript []
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

var minimumOperations = function (root) {
    const countSwaps = (arr) => {
        let sortedArr = [...arr].sort((a, b) => a - b);
        let indexMap = new Map();
        arr.forEach((val, i) => indexMap.set(val, i));
        let swaps = 0;

        for (let i = 0; i < arr.length; i++) {
            while (arr[i] !== sortedArr[i]) {
                swaps++;
                let targetIndex = indexMap.get(sortedArr[i]);
                [arr[i], arr[targetIndex]] = [arr[targetIndex], arr[i]];
                indexMap.set(arr[targetIndex], targetIndex);
                indexMap.set(arr[i], i);
            }
        }
        return swaps;
    };

    let count = 0;
    let queue = [root];
    while (queue.length > 0) {
        let level = [];
        let nextQueue = [];
        for (let node of queue) {
            level.push(node.val);
            if (node.left) nextQueue.push(node.left);
            if (node.right) nextQueue.push(node.right);
        }
        count += countSwaps(level);
        queue = nextQueue;
    }
    return count;
};
```
```cpp []
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        auto countSwaps = [](vector<int>& arr) {
            vector<int> sortedArr = arr;
            sort(sortedArr.begin(), sortedArr.end());
            unordered_map<int, int> indexMap;
            for (int i = 0; i < arr.size(); i++) {
                indexMap[arr[i]] = i;
            }

            int swaps = 0;
            for (int i = 0; i < arr.size(); i++) {
                while (arr[i] != sortedArr[i]) {
                    swaps++;
                    int targetIndex = indexMap[sortedArr[i]];
                    swap(arr[i], arr[targetIndex]);
                    indexMap[arr[targetIndex]] = targetIndex;
                    indexMap[arr[i]] = i;
                }
            }
            return swaps;
        };

        int count = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            vector<int> level;
            int size = q.size();
            for (int i = 0; i < size; 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 += countSwaps(level);
        }
        return count;
    }
};
``` 
```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 {
    public int minimumOperations(TreeNode root) {
        int count = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            int size = q.size();
            int[] arr1 = new int[size];
            int[] arr2 = new int[size];
            for(int i = 0; i < size; i++) {
                TreeNode temp = q.poll();
                arr1[i] = temp.val;
                arr2[i] = temp.val;
                if(temp.left != null) q.add(temp.left);
                if(temp.right != null) q.add(temp.right);
            }
            count += fun(arr1, arr2);
        }
        return count;
    }

    static int fun(int[] arr1, int[] arr2) {
        int n = arr1.length;
        if(n == 1) return 0;
        Arrays.sort(arr1);
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++) map.put(arr1[i], i);
        
        int count = 0;
        for(int i = 0; i < n; ) {
            int index = map.get(arr2[i]);
            if(index == i) i++;
            else {
                count++;
                int temp = arr2[i];
                arr2[i] = arr2[index];
                arr2[index] = temp;
            }
        }
        return count;
    }
}
```
---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}

['Tree', 'Breadth-First Search', 'Binary Tree', 'C++', 'Java', 'JavaScript', 'Dart']