Minimum Number of Operations to Sort a Binary Tree by Level

medium trees bfs cycle sort

Problem

You are given the root of a binary tree with unique values. In one operation you may pick any two nodes on the same level and swap their values. Return the minimum number of operations needed so that the values on every level read in strictly increasing order from left to right. The level of a node is the number of edges on the path from it to the root.

Inputroot = [1,3,2,7,6,5,4]

Output3

Level 1 [3,2] needs 1 swap; level 2 [7,6,5,4] needs 2 swaps; total 3.

Inputroot = [1,2,3,4,5,6]

Output0

Every level is already sorted, so no swaps are needed.

tree (level order, use x for null)

def minimum_operations(root):
    total = 0
    queue = [root]
    while queue:
        vals = [n.val for n in queue]
        target = sorted(vals)
        pos = {v: i for i, v in enumerate(target)}
        seen = [False] * len(vals)
        for i in range(len(vals)):
            if seen[i] or pos[vals[i]] == i:
                continue
            length = 0
            j = i
            while not seen[j]:
                seen[j] = True
                j = pos[vals[j]]
                length += 1
            total += length - 1
        nxt = []
        for n in queue:
            if n.left:
                nxt.append(n.left)
            if n.right:
                nxt.append(n.right)
        queue = nxt
    return total

function minimumOperations(root) {
  let total = 0;
  let queue = [root];
  while (queue.length) {
    const vals = queue.map(n => n.val);
    const target = [...vals].sort((a, b) => a - b);
    const pos = new Map(target.map((v, i) => [v, i]));
    const seen = new Array(vals.length).fill(false);
    for (let i = 0; i < vals.length; i++) {
      if (seen[i] || pos.get(vals[i]) === i) continue;
      let length = 0, j = i;
      while (!seen[j]) {
        seen[j] = true;
        j = pos.get(vals[j]);
        length++;
      }
      total += length - 1;
    }
    const nxt = [];
    for (const n of queue) {
      if (n.left) nxt.push(n.left);
      if (n.right) nxt.push(n.right);
    }
    queue = nxt;
  }
  return total;
}

int minimumOperations(TreeNode root) {
    int total = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int sz = queue.size();
        int[] vals = new int[sz];
        for (int k = 0; k < sz; k++) {
            TreeNode n = queue.poll();
            vals[k] = n.val;
            if (n.left != null) queue.add(n.left);
            if (n.right != null) queue.add(n.right);
        }
        int[] target = vals.clone();
        Arrays.sort(target);
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = 0; i < sz; i++) pos.put(target[i], i);
        boolean[] seen = new boolean[sz];
        for (int i = 0; i < sz; i++) {
            if (seen[i] || pos.get(vals[i]) == i) continue;
            int length = 0, j = i;
            while (!seen[j]) { seen[j] = true; j = pos.get(vals[j]); length++; }
            total += length - 1;
        }
    }
    return total;
}

int minimumOperations(TreeNode* root) {
    int total = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> vals(sz);
        for (int k = 0; k < sz; k++) {
            TreeNode* n = q.front(); q.pop();
            vals[k] = n->val;
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        vector<int> target = vals;
        sort(target.begin(), target.end());
        unordered_map<int, int> pos;
        for (int i = 0; i < sz; i++) pos[target[i]] = i;
        vector<bool> seen(sz, false);
        for (int i = 0; i < sz; i++) {
            if (seen[i] || pos[vals[i]] == i) continue;
            int length = 0, j = i;
            while (!seen[j]) { seen[j] = true; j = pos[vals[j]]; length++; }
            total += length - 1;
        }
    }
    return total;
}

Explanation

The levels are independent: a swap only moves values within one level, so we can minimize each level separately and add the costs. A breadth-first traversal visits the tree level by level, giving us the array of values currently on each level.

On one level, the question becomes: what is the minimum number of swaps to sort an array of distinct numbers? The classic answer is cycle decomposition. Build the permutation that says, for each current position, which sorted position that value belongs in.

That permutation breaks into disjoint cycles. A cycle of length L can be fixed with exactly L − 1 swaps (rotate each element into place one at a time). Elements already in the right spot are length-1 cycles costing zero.

So we map every value to its index in the sorted level (pos), then walk unvisited positions following i → pos[vals[i]] until we return to the start, counting the cycle length. We add length − 1 for every cycle and accumulate across all levels.

For [1,3,2,7,6,5,4]: level 1 [3,2] is one 2-cycle (1 swap); level 2 [7,6,5,4] is two 2-cycles (2 swaps). The total is 3.

Time: O(n log n) Space: O(n)