Minimum Operations to Sort Binary Tree by Level — LeetCode 2471 Cycle Sort

Problem Statement#

You are given the root of a binary tree with unique values. In one operation, you can swap the values of any two nodes that are on the same level. Return the minimum number of operations needed to make the values at every level sorted in strictly increasing order.

Constraints:

• The number of nodes in the tree is in the range [1, 10^5]
• 1 <= Node.val <= 10^5
• All values in the tree are unique

Input:  root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
Output: 3

Input:  root = [1,3,2,7,6,5,4]
Output: 3

Why This Problem Matters#

LeetCode 2471 — Minimum Number of Operations to Sort a Binary Tree by Level — sits at the intersection of BFS and the classic "minimum swaps to sort an array" subproblem. It is asked at Google, Meta, Amazon, and Microsoft because it cleanly tests two compositional skills: tree traversal to extract per-level arrays, and the cycle-decomposition technique for minimum swaps.

Engineers who recognize the cycle-sort subproblem solve it in 15 minutes; others spend most of the interview computing swaps incorrectly. The pattern matters in practice: reorder pages in a paginated cache, schedule jobs grouped by priority tier, or align rows in a UI tree.

The Core Insight#

Per level, the minimum number of swaps to sort an array of distinct values equals n - (number of cycles in the permutation that maps current positions to sorted positions). We BFS the tree level by level, extract the values, sort a copy to determine target positions, build a permutation (pos[val] = index in sorted), and count cycles by following each unvisited element until it returns to itself.

A faster equivalent: for each i, while arr[i] != sorted_arr[i], swap arr[i] with arr[pos[sorted_arr[i]]] and increment a swap counter. This avoids the explicit cycle decomposition.

Visual Dry Run#

Level values [7, 6, 8, 5] (sorted target [5, 6, 7, 8]):

Total swaps for that level: 2. Sum across levels gives the answer.

Solution (Optimal)#

from collections import deque
from typing import List, Optional
 
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 min_swaps(level: List[int]) -> int:
            indexed = sorted(range(len(level)), key=lambda i: level[i])
            visited = [False] * len(level)
            swaps = 0
            for i in range(len(level)):
                if visited[i] or indexed[i] == i:
                    continue
                cycle_len = 0
                j = i
                while not visited[j]:
                    visited[j] = True
                    j = indexed[j]
                    cycle_len += 1
                swaps += cycle_len - 1
            return swaps
 
        if root is None:
            return 0
        queue = deque([root])
        total = 0
        while queue:
            size = len(queue)
            level_vals = []
            for _ in range(size):
                node = queue.popleft()
                level_vals.append(node.val)
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            total += min_swaps(level_vals)
        return total

var minimumOperations = function(root) {
    const minSwaps = (level) => {
        const indexed = level
            .map((v, i) => [v, i])
            .sort((a, b) => a[0] - b[0])
            .map((p) => p[1]);
        const visited = new Array(level.length).fill(false);
        let swaps = 0;
        for (let i = 0; i < level.length; i++) {
            if (visited[i] || indexed[i] === i) continue;
            let cycleLen = 0;
            let j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = indexed[j];
                cycleLen += 1;
            }
            swaps += cycleLen - 1;
        }
        return swaps;
    };
 
    if (!root) return 0;
    const queue = [root];
    let total = 0;
    while (queue.length > 0) {
        const size = queue.length;
        const levelVals = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            levelVals.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        total += minSwaps(levelVals);
    }
    return total;
};

Time: O(n log n) — sorting each level dominates; total values summed across levels is n. Space: O(n) — queue and per-level arrays.

Common Mistakes#

• Counting "in-place" swaps rather than cycle-based minimum swaps; bubble-sort logic gives the wrong answer.
• Sorting the level in place and forgetting to track original indices for the permutation.
• Treating each cycle's length as the swap count; the correct formula is cycle_len - 1.
• BFS over a binary tree but pushing nulls into the queue, polluting per-level value arrays.
• Recomputing pos[val] inside the loop with linear scans, blowing up to O(n^2) per level.

Interview Tips#

• Decompose the problem aloud: "BFS to get per-level arrays, then minimum-swaps-to-sort each."
• Walk through cycle decomposition on an array of length 4.
• Mention that this problem is essentially LC 2471 = LC 102 Level Order + min-swaps-to-sort.
• If asked, derive the cycle_len - 1 formula via a 3-cycle example.

Follow-up Questions#

• "What if values can repeat?" — The cycle approach needs adjustment; use a multi-set match.
• "Allow only adjacent swaps within a level" — Becomes counting inversions, O(n log n) via merge sort.
• "Minimum operations to sort the entire BFS sequence regardless of level" — Reduces to single-array min swaps.
• "Online tree updates" — Re-run BFS or maintain per-level sorted structures with order statistics trees.
• "K-ary tree" — Same template, iterate node.children.

Key Takeaways#

• LeetCode 2471 Minimum Operations to Sort a Binary Tree by Level combines BFS with the cycle-decomposition minimum-swaps subroutine.
• Per level, minimum swaps to sort = n - number of cycles in the position permutation.
• Total time is O(n log n) due to per-level sort; space is O(n).
• The cycle-length formula contributes cycle_len - 1 swaps per cycle.
• Frequent at Google, Meta, and Amazon for tree plus algorithmic-subroutine composition.
• The same min-swaps-to-sort routine appears in LC 765 Couples Holding Hands and many array problems.
• Skipping fixed points (indexed[i] == i) keeps the inner loop tight.