C# Solution for Minimum Number of Operations To Sort A Binary Tree By Level Problem
IntuitionThe goal is to sort the values at each level of a binary tree with the minimum number of swap operations. Since swaps can only occur between nodes at t
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The goal is to sort the values at each level of a binary tree with the minimum number of swap operations. Since swaps can only occur between nodes at the same level, the problem reduces to finding the minimum number of swaps needed to sort an array (representing the values of a level). This is achieved using cycle detection in the permutation of indices from the original array to the sorted array.

# Approach
<!-- Describe your approach to solving the problem. -->
1.	Level Order Traversal (BFS):
	•	Perform a level-order traversal of the binary tree using a queue.
	•	At each level, store the node values in a list.
2.	Minimum Swaps for Sorting (Cycle Detection):
	•	For the values of a level, sort them to determine the target order.
	•	Map each value to its index in the sorted array to determine the “target position” of each element.
	•	Detect cycles in the mapping:
	•	A cycle represents a set of elements that must be rearranged among themselves to reach their correct positions.
	•	For a cycle of size k, k-1 swaps are required to resolve it.
3.	Count Total Swaps:
	•	Sum the swaps required for all levels.
4.	Return the Result:
	•	Return the total number of swaps.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
1.	Level Order Traversal:
	•	Visiting all nodes takes O(n), where n is the number of nodes in the tree.
2.	Sorting Each Level:
	•	For a level with k nodes, sorting takes O(k log k).
	•	Across all levels, the total sorting time is O(n log k_{max}), where k_max is the maximum number of nodes at any level.
3.	Cycle Detection:
	•	For a level with k nodes, detecting cycles takes O(k).
	•	Across all levels, the total time is O(n).
4.	Overall Complexity:
	•	Sorting dominates, so the total complexity is: O(n log k_max)

	•	In the worst case, where k_max ~= n / 2 (e.g., a complete binary tree), the complexity is: O(n log n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
1.	Queue for BFS:
	•	At most O(k_max) nodes are stored in the queue.
2.	Storage for Level Values:
	•	At most O(k_max) for the values of a single level.
3.	Auxiliary Data Structures:
	•	Sorting requires O(k_max) space for the array and mapping.
4.	Total Space Complexity:
	•	Dominated by O(k_max), worst case O(n).

# Code
```csharp []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MinimumOperations(TreeNode root) {
        if (root == null) return 0;

        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        int operations = 0;

        while (queue.Count > 0) {
            int size = queue.Count;
            var level = new List<int>();

            // Collect all nodes at the current level
            for (int i = 0; i < size; i++) {
                var node = queue.Dequeue();
                level.Add(node.val);

                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }

            // Calculate the minimum swaps needed for this level
            operations += CountMinSwaps(level);
        }

        return operations;
    }
    private int CountMinSwaps(List<int> level) {
        int n = level.Count;
        var arr = new int[n];
        var sortedArr = new int[n];

        // Copy values to arrays
        for (int i = 0; i < n; i++) {
            arr[i] = level[i];
            sortedArr[i] = level[i];
        }

        // Sort the array to get the target order
        Array.Sort(sortedArr);

        // Map each value to its index in the sorted array
        var indexMap = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            indexMap[sortedArr[i]] = i;
        }

        // Perform cycle detection to count swaps
        var visited = new bool[n];
        int swaps = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i] || indexMap[arr[i]] == i) continue;

            int cycleSize = 0;
            int j = i;

            while (!visited[j]) {
                visited[j] = true;
                j = indexMap[arr[j]];
                cycleSize++;
            }

            if (cycleSize > 1) swaps += cycleSize - 1;
        }

        return swaps;
    }
}
```
['C#']