Minimum Number of Operations to Sort a Binary Tree by Level
Minimum Operations to Sort Levels of a Binary TreeIntuitionThe problem involves finding the minimum number of operations required to make all levels of a binary
# Minimum Operations to Sort Levels of a Binary Tree

## Intuition
The problem involves finding the minimum number of operations required to make all levels of a binary tree sorted. Each operation involves swapping two elements in a level. Sorting the levels individually ensures a valid tree structure is preserved.

The intuition is:
1. Perform a level-order traversal of the tree.
2. For each level, determine the number of swaps required to sort its values.
3. Sum up these swaps across all levels.

---

## Approach

### Steps:
1. **Level-Order Traversal**:
   - Use a queue to traverse the tree level by level (Breadth-First Search).
   - For each level, collect the values into a list.

2. **Count Minimum Swaps**:
   - For each level, calculate the minimum number of swaps needed to sort the level using a helper function `cou`.

3. **Sum Up Results**:
   - Add the number of swaps for each level to get the total operations required.

### Helper Function: `cou`
- This function calculates the minimum number of swaps required to sort an array.
- Use a **HashMap** to store the original indices of elements.
- Iterate through the array and:
  - If the current element is not in the correct position, swap it with the element in its sorted position.
  - Update the HashMap accordingly.

### Edge Cases:
- If the tree is empty (`root == null`), return `0`.
- If a level has only one element, it is already sorted.

---

## Complexity

### Time Complexity:
1. **Level-Order Traversal**:
   - Visiting each node once: $$O(n)$$ where $$n$$ is the number of nodes in the tree.
2. **Sorting Each Level**:
   - For a level with $$m$$ nodes, sorting takes $$O(m \log m)$$ and finding swaps takes $$O(m)$$.
   - Across all levels, this is bounded by $$O(n \log n)$$ as the total number of elements across levels is $$n$$.

Overall Time Complexity: **$$O(n \log n)$$**

### Space Complexity:
1. **Queue for BFS**:
   - At most, it holds one level of nodes: $$O(w)$$ where $$w$$ is the maximum width of the tree.
2. **Lists for Each Level**:
   - Storing one level of values at a time: $$O(w)$$.
3. **HashMap for `cou`**:
   - Storing indices for each level: $$O(m)$$ where $$m$$ is the number of elements in a level.

Overall Space Complexity: **$$O(w)$$**

---

## Code

```java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public static int cou(ArrayList<Integer> l3, ArrayList<Integer> l4) {
        Collections.sort(l4);
        int c = 0;
        HashMap<Integer, Integer> r = new HashMap<>();
        for (int i = 0; i < l3.size(); i++) {
            r.put(l3.get(i), i);
        }

        for (int i = 0; i < l3.size(); i++) {
            if (!l3.get(i).equals(l4.get(i))) {
                int idx = r.get(l4.get(i));
                r.put(l3.get(i), idx);
                r.put(l3.get(idx), i);
                Collections.swap(l3, i, idx);
                c++;
            }
        }
        return c;
    }

    public int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(null);

        int sum = 0;
        ArrayList<Integer> l1 = new ArrayList<>();

        while (!q.isEmpty()) {
            TreeNode c = q.poll();

            if (c != null) {
                l1.add(c.val);

                if (c.left != null) {
                    q.add(c.left);
                }
                if (c.right != null) {
                    q.add(c.right);
                }
            } else {
                if (!l1.isEmpty()) {
                    ArrayList<Integer> sortedList = new ArrayList<>(l1);
                    sum += cou(l1, sortedList);
                    l1.clear();
                }

                if (!q.isEmpty()) {
                    q.add(null);
                }
            }
        }

        return sum;
    }
}
```


```java []

class Solution {
    public static int cou(ArrayList<Integer> l3, ArrayList<Integer> l4) {
        Collections.sort(l4);
        int c = 0;
        HashMap<Integer, Integer> r = new HashMap<>();
        for (int i = 0; i < l3.size(); i++) {
            r.put(l3.get(i), i);
        }

        for (int i = 0; i < l3.size(); i++) {
            if (!l3.get(i).equals(l4.get(i))) {
                int idx = r.get(l4.get(i));
                r.put(l3.get(i), idx);
                r.put(l3.get(idx), i);
                Collections.swap(l3, i, idx);
                c++;
            }
        }
        return c;
    }

    public int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(null);

        int sum = 0;
        ArrayList<Integer> l1 = new ArrayList<>();

        while (!q.isEmpty()) {
            TreeNode c = q.poll();

            if (c != null) {
                l1.add(c.val);

                if (c.left != null) {
                    q.add(c.left);
                }
                if (c.right != null) {
                    q.add(c.right);
                }
            } else {
                if (!l1.isEmpty()) {
                    ArrayList<Integer> sortedList = new ArrayList<>(l1);
                    sum += cou(l1, sortedList);
                    l1.clear();
                }

                if (!q.isEmpty()) {
                    q.add(null);
                }
            }
        }

        return sum;
    }
}

```
['Java']