BFS + Minimum Swaps using Cycle Detection , Graph in C++
IntuitionThe task is to ensure the binary tree is level-wise sorted with the minimum number of operations. Since we can only swap values within the same level,
# Intuition
The task is to ensure the binary tree is level-wise sorted with the minimum number of operations. Since we can only swap values within the same level, we must find the number of swaps required to sort each level of the tree.

### To achieve this, we can: 
- Traverse the tree level by level using Breadth-First Search (BFS).
- For each level, calculate the number of swaps required to sort the node values. This is achieved by detecting and breaking cycles in the unsorted array representation of the level.

---


# Approach
1. **Level-by-Level Traversal**:
    - Use BFS to traverse the tree level by level.
    - At each level, collect the node values and their indices into a vector.
2. **Sorting and Cycle Detection**:
    - Sort the values of the current level while keeping track of their original indices.
    - Use cycle detection to calculate the minimum number of swaps required to sort the values.
        - Iterate through the array. For each element, check if it's already visited or already in the correct position. Skip such elements.
        - If the element is not in the correct position, follow its cycle:
            - Start from the current element and follow the indices in the sorted array until you return to the starting element.
            - Count the number of elements in the cycle.
        - `To sort a cycle of size k, 𝑘−1 swaps are required.`
3. **Sum of Swaps**:
    - Add the swaps for each level to the result and move to the next level.
4. **Result**:
    - Return the total number of swaps required after processing all levels.

---


# Complexity
- **Time complexity:**
    - Traversing the tree: $$O(n)$$, where 𝑛 is the number of nodes.
    - sorting each level $$O(klogk)$$, where k is the number of nodes at that level.
    - Detecting cycles: $$O(k)$$ per level.
    - Overall complexity: $$O(n+klogk)$$, where k is the maximum number of nodes at any level.

- **Space complexity:**
    - BFS queue and arrPos vector: $$O(k)$$ per level.
    - Total space: $$O(k)$$, where k is the maximum number of nodes at any level.

---


# Code
```cpp []
/**
 * 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) {
        // Initialize a queue for BFS and a result variable to store the total swaps
        queue<TreeNode *> q;
        q.push(root);
        int res = 0;

        // Perform BFS traversal
        while (!q.empty()) {
            int n = q.size(); // Number of nodes at the current level
            vector<pair<int, int>> arrPos(n); // Vector to store node values and indices

            // Process all nodes at the current level
            for (int i = 0; i < n; i++) {
                TreeNode *front = q.front();
                q.pop();
                
                // Add children to the queue for the next level
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
                
                // Store the node value and its index
                arrPos[i] = {front->val, i};
            }

            // Sort the array by value while keeping track of original indices
            sort(arrPos.begin(), arrPos.end());

            // Track visited nodes for cycle detection
            vector<bool> visited(n, false);
            int swaps = 0;

            // Calculate the number of swaps required using cycle detection
            for (int i = 0; i < n; i++) {
                // Skip already visited or correctly placed nodes
                if (visited[i] || arrPos[i].second == i) continue;

                // Find the size of the cycle
                int cycleSize = 0;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = arrPos[j].second;
                    cycleSize++;
                }

                // Add swaps for the current cycle
                if (cycleSize > 1) {
                    swaps += (cycleSize - 1);
                }
            }

            // Update the total result with swaps for this level
            res += swaps;
        }

        // Return the total number of swaps
        return res;
    }
};
```
['Tree', 'Breadth-First Search', 'Graph', 'Binary Tree', 'C++']