# Minimum Number of Operations to Sort a Binary Tree by Level
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Guidewire](https://scaleengineer.com/companies/guidewire)
---
## Problem
You are given the `root` of a binary tree with **unique values**.

In one operation, you can choose any two nodes **at the same level** and swap their values.

Return _the minimum number of operations needed to make the values at each level sorted in a **strictly increasing order**_.

The **level** of a node is the number of edges along the path between it and the root node_._

**Example 1:**

![](https://assets.glich.co/dsa/minimum-number-of-operations-to-sort-a-binary-tree-by-level/image0.png) 

**Input:** root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
**Output:** 3
**Explanation:**
- Swap 4 and 3. The 2nd level becomes [3,4].
- Swap 7 and 5. The 3rd level becomes [5,6,8,7].
- Swap 8 and 7. The 3rd level becomes [5,6,7,8].
We used 3 operations so return 3.
It can be proven that 3 is the minimum number of operations needed.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-number-of-operations-to-sort-a-binary-tree-by-level/image1.png) 

**Input:** root = [1,3,2,7,6,5,4]
**Output:** 3
**Explanation:**
- Swap 3 and 2. The 2nd level becomes [2,3].
- Swap 7 and 4. The 3rd level becomes [4,6,5,7].
- Swap 6 and 5. The 3rd level becomes [4,5,6,7].
We used 3 operations so return 3.
It can be proven that 3 is the minimum number of operations needed.

**Example 3:**

![](https://assets.glich.co/dsa/minimum-number-of-operations-to-sort-a-binary-tree-by-level/image2.png) 

**Input:** root = [1,2,3,4,5,6]
**Output:** 0
**Explanation:** Each level is already sorted in increasing order so return 0.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 105]`.
* `1 <= Node.val <= 105`
* All the values of the tree are **unique**.

# Approaches
## Level Order Traversal with Selection Sort
This approach processes the tree level by level using Breadth-First Search (BFS). For each level, it collects all node values into a list. Then, it calculates the minimum swaps required to sort this list using a method analogous to Selection Sort. The number of swaps performed by Selection Sort is known to be the minimum required to sort an array. The total number of operations is the sum of swaps required for each level.
**Time:** O(N^2) in the worst case. The level order traversal itself takes O(N) time, where N is the total number of nodes. For each level with `k` nodes, the `countSwaps` function, which implements Selection Sort, takes O(k^2) time. In a complete binary tree, the last level can have about N/2 nodes, making the complexity for that single level O((N/2)^2) = O(N^2). This dominates the overall time complexity. · **Space:** O(W), where W is the maximum width of the binary tree. This space is required for the BFS queue and the list to store the values of the nodes at a single level. In the worst case of a complete binary tree, W can be proportional to N, making the space complexity O(N).
**Pros:** The approach is straightforward and relatively easy to understand and implement.; It correctly breaks down the problem into independent subproblems for each level.
**Cons:** The time complexity for sorting each level is `O(k^2)`, where `k` is the number of nodes at that level. This can lead to an overall time complexity of `O(N^2)` for a balanced tree, which is inefficient and may time out on larger test cases.
### Explanation
The algorithm begins with a standard level order traversal using a queue. In each step of the traversal, we process all nodes at the current level. The values of these nodes are collected into a temporary list. To find the minimum number of swaps for this list, we apply the logic of Selection Sort. We iterate through the list from left to right. For each position `i`, we find the smallest element in the rest of the list (from `i` to the end). If this smallest element is not already at position `i`, we swap it into place and count it as one operation. This process is repeated for every level, and the swap counts from each level are summed up to get the final result.

```java
class Solution {
    public int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int operations = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> levelValues = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelValues.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            operations += countSwaps(levelValues);
        }
        return operations;
    }

    // Counts swaps using Selection Sort logic
    private int countSwaps(List<Integer> arr) {
        int n = arr.size();
        int swaps = 0;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr.get(j) < arr.get(minIndex)) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                Collections.swap(arr, i, minIndex);
                swaps++;
            }
        }
        return swaps;
    }
}
```
### Algorithm
*   Initialize `total_swaps = 0`.
*   If the `root` is null, return 0.
*   Create a queue for Level Order Traversal and add the `root` node.
*   Loop while the queue is not empty:
    *   Determine the number of nodes at the current level, `level_size`.
    *   Create a list, `level_values`, to store the values of nodes at this level.
    *   Dequeue `level_size` nodes. For each node, add its value to `level_values` and enqueue its non-null children.
    *   Calculate the number of swaps needed to sort `level_values` using a Selection Sort-like process:
        *   Initialize `level_swaps = 0`.
        *   Iterate with index `i` from 0 to the second to last element of `level_values`.
        *   In each iteration, find the index `min_idx` of the smallest element in the sublist starting from `i`.
        *   If `min_idx` is not equal to `i`, it means the element at `i` is not the smallest possible. Swap the elements at `i` and `min_idx`, and increment `level_swaps`.
    *   Add `level_swaps` to `total_swaps`.
*   Return `total_swaps`.

## Level Order Traversal with Cycle Sort
This optimized approach also uses BFS to process the tree level by level. However, it employs a more efficient algorithm to count the minimum swaps for each level's values. The problem of finding the minimum swaps to sort an array is equivalent to finding the number of cycles in its permutation. The minimum number of swaps is `k - C`, where `k` is the number of elements and `C` is the number of cycles. This can be implemented efficiently by creating a sorted version of the level's values and using a hash map to track the positions of elements, bringing them to their correct sorted positions one by one.
**Time:** O(N log N). The BFS traversal takes O(N). For each level with `k` nodes, the dominant operation is sorting the list of values, which takes O(k log k). The sum of `k_i * log(k_i)` over all levels `i` (where `sum(k_i) = N`) is bounded by O(N log N). The subsequent swapping loop takes O(k) time per level. Thus, the total time complexity is O(N log N). · **Space:** O(W), where W is the maximum width of the tree. This space is used for the BFS queue, the list for level values, its sorted copy, and the hash map. In the worst case of a complete binary tree, W can be O(N).
**Pros:** Highly efficient, with a time complexity that can handle large inputs.; It is guaranteed to find the minimum number of swaps based on the cycle decomposition of permutations.
**Cons:** The implementation is more complex than the naive selection sort approach, requiring extra space for a sorted copy and a hash map.; Requires careful management of values and their indices during the swapping process.
### Explanation
The algorithm traverses the tree using BFS. For each level, it gathers the node values into a list `level_values`. To find the minimum swaps for this list of size `k`, we first create a sorted copy, `sorted_values`, to know the target state. We also use a `HashMap` to store the current index of each value, allowing for O(1) lookups.

We then iterate from `i = 0` to `k-1`. If the element at `level_values.get(i)` is not what it should be (i.e., not equal to `sorted_values.get(i)`), we know a swap is necessary. We find the element that *should* be at index `i` (which is `sorted_values.get(i)`) and swap it with the current element. The hash map is used to quickly find the index of the element we need to swap with. After each swap, we update the hash map to reflect the new positions of the swapped elements. The total count of such swaps gives the minimum for that level.

```java
class Solution {
    public int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int operations = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> levelValues = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelValues.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            operations += countSwaps(levelValues);
        }
        return operations;
    }

    private int countSwaps(List<Integer> arr) {
        int n = arr.size();
        if (n <= 1) {
            return 0;
        }

        List<Integer> sortedArr = new ArrayList<>(arr);
        Collections.sort(sortedArr);

        Map<Integer, Integer> valToIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIndex.put(arr.get(i), i);
        }

        int swaps = 0;
        for (int i = 0; i < n; i++) {
            if (!arr.get(i).equals(sortedArr.get(i))) {
                swaps++;
                int val1 = arr.get(i);
                int val2 = sortedArr.get(i);

                int index2 = valToIndex.get(val2);

                // Swap in the array
                arr.set(i, val2);
                arr.set(index2, val1);

                // Update map for the two swapped values
                valToIndex.put(val1, index2);
                valToIndex.put(val2, i);
            }
        }
        return swaps;
    }
}
```
### Algorithm
*   Initialize `total_swaps = 0`.
*   If the `root` is null, return 0.
*   Create a queue for Level Order Traversal and add the `root` node.
*   Loop while the queue is not empty:
    *   Determine the number of nodes at the current level, `level_size`.
    *   Create a list, `level_values`, to store the values of nodes at this level.
    *   Dequeue `level_size` nodes, add their values to `level_values`, and enqueue their children.
    *   Calculate swaps for `level_values` (of size `k`) using a cycle sort approach:
        *   Create a sorted copy of the list, `sorted_values`.
        *   Create a `HashMap` `val_to_idx` to map each value in `level_values` to its current index.
        *   Initialize `level_swaps = 0`.
        *   Iterate with index `i` from 0 to `k-1`:
            *   If the value at `level_values[i]` is not the same as `sorted_values[i]`, it means the element is misplaced.
            *   Increment `level_swaps`.
            *   Identify the `current_val` at `level_values[i]` and the `correct_val` that should be at this position (`sorted_values[i]`).
            *   Find the index of `correct_val` using the `val_to_idx` map.
            *   Swap the elements in `level_values`.
            *   Update the `val_to_idx` map for the two values that were swapped.
    *   Add `level_swaps` to `total_swaps`.
*   Return `total_swaps`.

# Solutions
### Java

```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 ) { Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); int ans = 0 ; while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } ans += f ( t ); } return ans ; } private int f ( List < Integer > t ) { int n = t . size (); List < Integer > alls = new ArrayList <>( t ); alls . sort (( a , b ) -> a - b ); Map < Integer , Integer > m = new HashMap <>(); for ( int i = 0 ; i < n ; ++ i ) { m . put ( alls . get ( i ), i ); } int [] arr = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { arr [ i ] = m . get ( t . get ( i )); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { while ( arr [ i ] != i ) { swap ( arr , i , arr [ i ]); ++ ans ; } } return ans ; } private void swap ( int [] arr , int i , int j ) { int t = arr [ i ]; arr [ i ] = arr [ j ]; arr [ j ] = t ; } }
```

### CPP

```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 ) { queue < TreeNode *> q { { root } }; int ans = 0 ; auto f = []( vector < int >& t ) { int n = t . size (); vector < int > alls ( t . begin (), t . end ()); sort ( alls . begin (), alls . end ()); unordered_map < int , int > m ; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) m [ alls [ i ]] = i ; for ( int i = 0 ; i < n ; ++ i ) t [ i ] = m [ t [ i ]]; for ( int i = 0 ; i < n ; ++ i ) { while ( t [ i ] != i ) { swap ( t [ i ], t [ t [ i ]]); ++ ans ; } } return ans ; }; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n ; -- n ) { auto node = q . front (); q . pop (); t . emplace_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans += f ( t ); } return ans ; } };
```

### Python

```python
# 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 : Optional [ TreeNode ]) -> int : def swap ( arr , i , j ): arr [ i ], arr [ j ] = arr [ j ], arr [ i ] def f ( t ): n = len ( t ) m = { v : i for i , v in enumerate ( sorted ( t ))} for i in range ( n ): t [ i ] = m [ t [ i ]] ans = 0 for i in range ( n ): while t [ i ] != i : swap ( t , i , t [ i ]) ans += 1 return ans q = deque ([ root ]) ans = 0 while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans += f ( t ) return ans
```