Python | BFS & Cycle Detection in a Permutation
see the Successfully Accepted SubmissionCodeSteps

Traverse the Tree Level-by-Level:
Use a breadth-first search (BFS) approach to extract all nodes level by lev
[see the Successfully Accepted Submission](https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/submissions/1485835512/?envType=daily-question&envId=2024-12-23)

# Code
```python3 []

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        def min_swaps_to_sort(arr: List[int]) -> int:
            n = len(arr)
            indexed_arr = [(val, i) for i, val in enumerate(arr)]
            indexed_arr.sort()  # Sort by value
            visited = [False] * n
            swaps = 0

            for i in range(n):
                if visited[i] or indexed_arr[i][1] == i:
                    continue

                cycle_size = 0
                x = i

                while not visited[x]:
                    visited[x] = True
                    x = indexed_arr[x][1]
                    cycle_size += 1

                if cycle_size > 1:
                    swaps += cycle_size - 1

            return swaps

        queue = deque([root])
        total_swaps = 0

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)

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

            total_swaps += min_swaps_to_sort(current_level)

        return total_swaps

```

### Steps

1. **Traverse the Tree Level-by-Level:**
   Use a breadth-first search (BFS) approach to extract all nodes level by level. At each level, we gather the node values.

2. **Sort the Values Using Minimum Swaps:**
   For each level, determine the minimum number of swaps required to sort the values in strictly increasing order. This can be calculated using cycle decomposition in a permutation.

3. **Sum Up Swaps Across All Levels:**
   Keep track of the swaps needed for each level and return the total as the result.

### Explanation of the Code

#### `min_swaps_to_sort`:
- The function calculates the minimum number of swaps required to sort an array using the concept of cycle decomposition in a permutation.
- It works by tracking visited nodes in a permutation graph and counting the size of each cycle.

#### Tree Traversal:
- We perform a level-order traversal (BFS) of the binary tree using a queue.
- For each level, we extract the node values and pass them to `min_swaps_to_sort` to compute the swaps needed to sort them.

#### Accumulate Results:
- The total swaps across all levels are summed up and returned as the final result.

### Complexity Analysis

#### Time Complexity:
- **BFS traversal:** 
  \(O(n)\), where \(n\) is the number of nodes in the tree.
- **Sorting and cycle detection:** 
  \(O(k \log k)\) per level, where \(k\) is the number of nodes at that level.
- **Overall:** 
  \(O(n + k \log k)\) \(\approx O(n \log n)\).

#### Space Complexity:
- **BFS queue:** 
  \(O(w)\), where \(w\) is the maximum width of the tree.
- **Auxiliary arrays:** 
  \(O(k)\) per level.
- **Total:** 
  \(O(w + k)\).


![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']