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^51 <= Node.val <= 10^5all node values are distinct
Hints for Minimum Number of Operations to Sort a Binary Tree by Level
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.
Hint 2
For one level you need the minimum number of swaps that sorts an array of distinct values — a classic permutation question.
Hint 3
Map each position to the position its value occupies after sorting. That permutation splits into cycles; a cycle of length
Lcosts exactlyL - 1swaps.
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
- Walk the tree level by level, collecting each level's values in left-to-right order.
- For a level of
mvalues, sort the indices by value:order[j]is the index of the value that belongs at positionj. - Follow the permutation
j → order[j]from every unvisited index, marking indices; each walk traces one cycle. - Add
m - cyclesto 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 opsJava
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)