Minimum Number of Operations to Sort a Binary Tree by Level

Medium
1959.

Minimum Number of Operations to Sort a Binary Tree by Level

Minimum Number of Operations to Sort a Binary Tree by Level is a medium coding problem on sorting, breadth-first search and trees, asked in Amazon interviews.

You are given the root of a binary tree whose node values are all distinct.

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 left to right, are in strictly increasing order.

Example 1

Input
root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
Output
3
Explanation
Level 2 [4,3] needs one swap. Level 3 [7,6,8,5] needs two: swap 7 and 5 to get [5,6,8,7], then 8 and 7. Level 4 [9,10] is already sorted. Total 3.

Example 2

Input
root = [1,3,2,7,6,5,4]
Output
3
Explanation
Level 2 needs one swap; level 3 [7,6,5,4] needs two (7↔4, 6↔5). Total 3.

Example 3

Input
root = [1,2,3,4,5,6]
Output
0
Explanation
Every level is already increasing.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minimumOperations = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Operations to Sort a Binary Tree by Level Solution

Minimum Number of Operations to Sort a Binary Tree by Level solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Operations to Sort a Binary Tree by Level is a medium coding problem on sorting, breadth-first search and trees, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Sorting, Breadth-First Search, Trees
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the root of a binary tree whose node values are all distinct.

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 left to right, are in strictly increasing order.

Example 1

Input: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
Output: 3
Explanation: Level 2 [4,3] needs one swap. Level 3 [7,6,8,5] needs two: swap 7 and 5 to get [5,6,8,7], then 8 and 7. Level 4 [9,10] is already sorted. Total 3.

Example 2

Input: root = [1,3,2,7,6,5,4]
Output: 3
Explanation: Level 2 needs one swap; level 3 [7,6,5,4] needs two (7↔4, 6↔5). Total 3.

Example 3

Input: root = [1,2,3,4,5,6]
Output: 0
Explanation: Every level is already increasing.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct

Hints for Minimum Number of Operations to Sort a Binary Tree by Level

  1. Hint 1

    Levels never interact: a swap only ever involves two nodes of one level, so solve each level on its own and add the answers.

  2. Hint 2

    For one level you need the minimum number of swaps that sorts an array of distinct values — a classic permutation question.

  3. Hint 3

    Map each position to the position its value occupies after sorting. That permutation splits into cycles; a cycle of length L costs exactly L - 1 swaps.

How to solve Minimum Number of Operations to Sort a Binary Tree by Level

Collect each level with a breadth-first walk. For a level, sorting defines a permutation from current positions to target positions; the minimum number of swaps to apply a permutation is the number of elements minus the number of its cycles.

Approach

  1. Walk the tree level by level, collecting each level's values in left-to-right order.
  2. For a level of m values, sort the indices by value: order[j] is the index of the value that belongs at position j.
  3. Follow the permutation j → order[j] from every unvisited index, marking indices; each walk traces one cycle.
  4. Add m - cycles to the answer, and move on to the next level.

Why it works

A swap can join two cycles into one or split one into two, so it changes the cycle count by exactly one. The sorted arrangement is the permutation with m cycles (every element fixed), so at least m - cycles swaps are needed; swapping an element straight into its target position always splits off a fixed point, which reaches that bound.

Complexity

  • Time — O(n log n) — each level is sorted once
  • Space — O(n) for a level's values and the visited marks

Pitfalls

  • Counting inversions or adjacent swaps gives the wrong answer — any two nodes of a level may be swapped.
  • Values are only compared within a level; the levels need not be increasing relative to each other.

Reference solution

Python

from typing import Optional

def minimumOperations(root: Optional[TreeNode]) -> int:
    ops = 0
    level = [root] if root else []
    while level:
        vals = [node.val for node in level]
        m = len(vals)
        order = sorted(range(m), key=lambda i: vals[i])
        seen = [False] * m
        for i in range(m):
            if seen[i]:
                continue
            length = 0
            j = i
            while not seen[j]:
                seen[j] = True
                j = order[j]
                length += 1
            ops += length - 1
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
    return ops

Java

public static int minimumOperations(TreeNode root) {
    int ops = 0;
    List<TreeNode> level = new ArrayList<>();
    if (root != null) level.add(root);
    while (!level.isEmpty()) {
        int m = level.size();
        long[] keys = new long[m];
        for (int i = 0; i < m; i++) keys[i] = (long) level.get(i).val * 200000L + i;
        Arrays.sort(keys);
        int[] order = new int[m];
        for (int i = 0; i < m; i++) order[i] = (int) (keys[i] % 200000L);
        boolean[] seen = new boolean[m];
        for (int i = 0; i < m; i++) {
            if (seen[i]) continue;
            int len = 0, j = i;
            while (!seen[j]) { seen[j] = true; j = order[j]; len++; }
            ops += len - 1;
        }
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : level) {
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        level = next;
    }
    return ops;
}

C++

int minimumOperations(TreeNode* root) {
    int ops = 0;
    vector<TreeNode*> level;
    if (root) level.push_back(root);
    while (!level.empty()) {
        int m = (int) level.size();
        vector<int> order(m);
        for (int i = 0; i < m; i++) order[i] = i;
        sort(order.begin(), order.end(), [&](int a, int b) { return level[a]->val < level[b]->val; });
        vector<bool> seen(m, false);
        for (int i = 0; i < m; i++) {
            if (seen[i]) continue;
            int len = 0, j = i;
            while (!seen[j]) { seen[j] = true; j = order[j]; len++; }
            ops += len - 1;
        }
        vector<TreeNode*> next;
        for (TreeNode* node : level) {
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        level = next;
    }
    return ops;
}

JavaScript

var minimumOperations = function(root) {
    var ops = 0;
    var level = root === null ? [] : [root];
    while (level.length > 0) {
        var m = level.length, vals = [], order = [], seen = [], i;
        for (i = 0; i < m; i++) { vals.push(level[i].val); order.push(i); seen.push(false); }
        order.sort(function(a, b) { return vals[a] - vals[b]; });
        for (i = 0; i < m; i++) {
            if (seen[i]) continue;
            var len = 0, j = i;
            while (!seen[j]) { seen[j] = true; j = order[j]; len++; }
            ops += len - 1;
        }
        var next = [];
        for (i = 0; i < m; i++) {
            if (level[i].left !== null) next.push(level[i].left);
            if (level[i].right !== null) next.push(level[i].right);
        }
        level = next;
    }
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 274 sorting problems · the whole catalogue

Learn the technique: Sorting Algorithms · Breadth-First Search (BFS)