 💡 💡 Best solution ~ Not Easy using Cycle Decomposition Algorithm 🔄
🧠 Approach +  Intuition1️⃣ BFS (Level-order Traversal) with Queue 🧑‍💻We start by performing Breadth-First Search (BFS) to traverse the tree level-by-level:
The
![image.png](https://assets.leetcode.com/users/images/2bce7c28-ef85-4482-b3bd-3ad0fe3d9a40_1734914957.8927097.png)

# 🧠 Approach +  Intuition 


### 1️⃣ **BFS (Level-order Traversal) with Queue** 🧑‍💻

We start by performing **Breadth-First Search (BFS)** to traverse the tree **level-by-level**:
- The BFS helps us process all nodes at a given level together, so we can collect their values and calculate how many swaps are needed to sort them.
- **Queue** is used for BFS to store nodes that need to be processed. We process nodes one by one and add their left and right children (if they exist) to the queue.


### 2️⃣ **Find Minimum Swaps for Each Level** 🔄

For each level, once we have the node values, we calculate how many swaps are needed to sort them using the `minSwapsToSort` function.


---


`I recently used this method in codeforces contest so used this u can use inversion approach as well`

---


#### 💡 **Cycle-based Approach to Calculate Minimum Swaps**:
- In the `minSwapsToSort` function:
  - We pair each value with its original index.
  - We then sort the array based on the values and track which element needs to go to which position.
  - Using **cycle decomposition**:
    - Each cycle represents a group of elements that can be sorted with a set of swaps.
    - If an element is already in its correct position, it forms a cycle of length 1, so no swaps are needed.
    - For a cycle of length `k`, **k-1 swaps** are needed to sort the cycle.
  - This way, we find how many swaps are needed for sorting the current level.

### 3️⃣ **Accumulate the Total Swaps** 🏗️

After calculating the minimum swaps for the current level, we add it to the **total swap count**. We repeat this process for each level in the tree until all levels are processed.

### ⏱️ **Time Complexity (TC)**

1. **Level-order traversal (BFS)**:
    - The BFS traverses all nodes in the binary tree exactly once. 
    - If there are `n` nodes in total, BFS will take **O(n)** time.
    - At each level, we add the left and right child of each node (if they exist) to the queue, so each node is processed once.

2. **`minSwapsToSort` Function**:
    - For each level, we collect node values and use the `minSwapsToSort` function to calculate the minimum swaps required to sort the array.
    - This function involves sorting the array and identifying cycles. Sorting takes **O(k log k)**, where `k` is the number of nodes at the current level.
    - Since the total number of nodes is `n`, the sum of swaps for all levels is **O(n log n)** in the worst case.

### 🏗️ **Final Time Complexity**:  
- The time complexity for BFS traversal is **O(n)**.
- The time complexity for sorting and computing swaps at each level is **O(n log n)** (since sorting dominates the complexity).
- Thus, the **total time complexity** is:  
**O(n log n)**. 

### 💾 **Space Complexity (SC)**

1. **Queue for BFS**:
    - The maximum number of nodes at any level can be at most **O(n)** in the worst case.
    - The queue stores nodes for the current level, so it takes **O(n)** space.

2. **Auxiliary space for `minSwapsToSort`**:
    - At each level, we store the values of the nodes in a vector. In the worst case, this can take **O(n)** space for the entire tree.

### 🏗️ **Final Space Complexity**:
- The space complexity for BFS is **O(n)**.
- The space for the vector holding the node values at each level is **O(n)**.
- Thus, the **total space complexity** is:  
**O(n)**.

---


# Code
```cpp []
#include <iostream>
#include <vector>
#include <queue>
#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 minSwapsToSort(vector<int>& arr) {
        int n = arr.size();  // Get the size of the array
        vector<pair<int, int>> arrPos(n);  // This will store the value and original index
        
        // Step 1: Create a pair of (value, index) for each element in the array
        for (int i = 0; i < n; i++) {
            arrPos[i] = {arr[i], i};
        }
        
        // Step 2: Sort the array based on the values, not the original indices
        sort(arrPos.begin(), arrPos.end());
        
        // Step 3: Initialize visited array to mark elements that have already been placed correctly
        vector<bool> visited(n, false);
        
        int swaps = 0;  // Initialize swap counter
        
        // Step 4: Loop through each element of the array
        for (int i = 0; i < n; i++) {
            // If already visited or already in the correct position, skip this element
            if (visited[i] || arrPos[i].second == i) {
                continue;  // Skip this cycle
            }
            
            // Step 5: Find the cycle size
            int cycle_size = 0;
            int j = i;
            
            // While the element is not visited, we follow the cycle
            while (!visited[j]) {
                visited[j] = true;  // Mark the element as visited
                j = arrPos[j].second;  // Move to the next element in the cycle (based on original index)
                cycle_size++;  // Increase the cycle size
            }
            
            // Step 6: If the cycle size is greater than 1, add (cycle_size - 1) to the swaps count
            if (cycle_size > 1) {
                swaps += (cycle_size - 1);  // To sort a cycle of length k, we need (k-1) swaps
            }
        }
        
        return swaps;  // Return the total swaps needed
    }

    int minimumOperations(TreeNode* root) {
        if (root == nullptr) return 0;

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

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

            // Process the current level
            while (n--) {
                TreeNode* elem = q.front();
                q.pop();

                // Only add non-null children
                if (elem->left != nullptr) {
                    q.push(elem->left);
                    currnodes.push_back(elem->left->val);
                }
                if (elem->right != nullptr) {
                    q.push(elem->right);
                    currnodes.push_back(elem->right->val);
                }
            }

            // Apply the minSwapsToSort function to the values of the current level
            count += minSwapsToSort(currnodes);
        }
        
        return count;
    }
};

```
['Binary Search', 'Tree', 'Breadth-First Search', 'Binary Tree', 'C++']