Minimum Number of Operations to Sort Binary Tree by Level

# Python
from collections import deque

def minimumOperations(root):
    def min_swaps(arr):
        # min swaps to sort = n - num_cycles
        n = len(arr)
        indexed = sorted(range(n), key=lambda i: arr[i])
        visited = [False] * n
        cycles = 0
        for i in range(n):
            if visited[i] or indexed[i] == i:
                if not visited[i]:
                    cycles += 1
                    visited[i] = True
                continue
            cycle_len = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = indexed[j]
                cycle_len += 1
            cycles += 1
        return n - cycles

    total = 0
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        total += min_swaps(level)
    return total

// C++
int minSwaps(vector<int>& arr) {
    int n = arr.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){ return arr[a] < arr[b]; });
    vector<bool> vis(n, false);
    int cycles = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i] || idx[i] == i) { if(!vis[i]){cycles++;vis[i]=true;} continue; }
        int j = i;
        while (!vis[j]) { vis[j] = true; j = idx[j]; }
        cycles++;
    }
    return n - cycles;
}
int minimumOperations(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int total = 0;
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        while (sz--) {
            auto node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        total += minSwaps(level);
    }
    return total;
}

// Java
int minSwaps(int[] arr) {
    int n = arr.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> arr[a] - arr[b]);
    boolean[] vis = new boolean[n];
    int cycles = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i] || idx[i] == i) { if (!vis[i]) { cycles++; vis[i] = true; } continue; }
        int j = i;
        while (!vis[j]) { vis[j] = true; j = idx[j]; }
        cycles++;
    }
    return n - cycles;
}
public int minimumOperations(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    int total = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        int[] level = new int[sz];
        for (int i = 0; i < sz; i++) {
            TreeNode node = q.poll();
            level[i] = node.val;
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        total += minSwaps(level);
    }
    return total;
}

// JavaScript
function minimumOperations(root) {
    function minSwaps(arr) {
        const n = arr.length;
        const idx = [...Array(n).keys()].sort((a, b) => arr[a] - arr[b]);
        const vis = Array(n).fill(false);
        let cycles = 0;
        for (let i = 0; i < n; i++) {
            if (vis[i] || idx[i] === i) { if (!vis[i]) { cycles++; vis[i] = true; } continue; }
            let j = i;
            while (!vis[j]) { vis[j] = true; j = idx[j]; }
            cycles++;
        }
        return n - cycles;
    }
    let queue = [root], total = 0;
    while (queue.length) {
        total += minSwaps(queue.map(n => n.val));
        queue = queue.flatMap(n => [n.left, n.right].filter(Boolean));
    }
    return total;
}