Minimum Number of Operations to Sort a Binary Tree by Level solution and explanation
Google
9 more videos on this problem
Minimum Number of Operations to Sort a Binary Tree by Level | Leetcode 2471 | codestorywithMIKcodestorywithMIK · 24:36 · 8K views
Minimum Number of Operations to Sort a Binary Tree by Level - Leetcode 2471 - PythonNeetCodeIO · 14:45 · 8K views
Minimum Number of Operations to Sort a Binary Tree by Level | Leetcode 2471Techdose · 27:35 · 3K views
2471. Minimum Number of Operations to Sort a Binary Tree by Level | Arrays & TreeAryan Mittal · 11:28 · 2K views
2471. Minimum Number of Operations to Sort a Binary Tree by Level | Weekly 319 | LeetCode 2471Bro Coders · 14:21 · 2K views
2471. Minimum Number of Operations to Sort a Binary Tree by Level (Leetcode Medium)Programming Live with Larry · 19:15 · 673 views
2471. Minimum Number of Operations to Sort a Binary Tree by Level | Leetcode Daily 23/12/2024 | JavaAlgorithmHQ · 16:14 · 621 views
Daily Leetcode #1728: Dec 23, 2024 - 2471. Minimum Number of Operations to Sort a Binary Tree...Programming Live with Larry · 10:13 · 373 views
Leetcode Weekly contest 319 - Medium - Minimum Number of Operations to Sort a Binary Tree by LevelPrakhar Agrawal · 10:32 · 346 views
2471. Minimum Number of Operations to Sort a Binary Tree by Level | LEETCODE MEDIUM | BINARY TREEcode Explainer · 14:03 · 300 views
The problem
You are given the root of a binary tree with unique values.
In one operation, you can choose any two nodes at the same level and swap their values.
Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order.
The level of a node is the number of edges along the path between it and the root node.
Example 1:
Input: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10] Output: 3 Explanation: - Swap 4 and 3. The 2nd level becomes [3,4]. - Swap 7 and 5. The 3rd level becomes [5,6,8,7]. - Swap 8 and 7. The 3rd level becomes [5,6,7,8]. We used 3 operations so return 3. It can be proven that 3 is the minimum number of operations needed.
Example 2:
Input: root = [1,3,2,7,6,5,4] Output: 3 Explanation: - Swap 3 and 2. The 2nd level becomes [2,3]. - Swap 7 and 4. The 3rd level becomes [4,6,5,7]. - Swap 6 and 5. The 3rd level becomes [4,5,6,7]. We used 3 operations so return 3. It can be proven that 3 is the minimum number of operations needed.
Example 3:
Input: root = [1,2,3,4,5,6] Output: 0 Explanation: Each level is already sorted in increasing order so return 0.
Constraints:
- The number of nodes in the tree is in the range
[1, 105]. 1 <= Node.val <= 105- All the values of the tree are unique.
Approach overview
Problem Overview: Each level of a binary tree must be sorted in strictly increasing order. You can swap values between any two nodes within the same level. The goal is to compute the minimum number of swaps required across all levels.
Approach 1: BFS + Cycle Detection (O(n log n) time, O(n) space)
Traverse the tree level by level using Breadth-First Search. For each level, collect node values into an array. To determine the minimum swaps required to sort that array, pair each value with its original index, sort by value, then detect permutation cycles. A cycle of length k requires k - 1 swaps. Summing swaps for all cycles gives the minimum operations for that level.
The key insight: sorting defines the target position of every element, and the mismatch between current and sorted indices forms permutation cycles. BFS naturally isolates each level, while cycle detection converts the reordering problem into a minimum swap count. Sorting each level costs O(m log m) where m is the level size, leading to O(n log n) overall.
Approach 2: DFS Level Collection + In-Place Reordering (O(n log n) time, O(n) space)
Run a DFS on the tree while tracking depth. Store values for each depth in a list so you reconstruct level order without BFS. Once all levels are collected, process each array independently. Build a sorted copy, map values to indices, and perform in-place swaps until every element reaches its sorted position.
This approach separates traversal from sorting logic. DFS builds level buckets, and the swap phase repeatedly places the correct value at index i. Each swap fixes at least one element, ensuring minimal operations. Like the BFS method, sorting dominates runtime at O(n log n). Space usage remains linear due to recursion stack and level storage. The tree traversal itself relies on standard binary tree recursion.
Recommended for interviews: The BFS + cycle detection approach is the most direct and typically expected. Interviewers want to see two insights: process the tree level-by-level and compute minimum swaps using permutation cycles. The DFS variant demonstrates flexibility in traversal strategies, but the BFS solution communicates the level-based nature of the problem more clearly.
Approach 1: Approach with BFS and Cycles
This approach involves performing a breadth-first search (BFS) to traverse the tree level by level. For each level, extract the nodes and determine the minimum number of swaps required to sort the nodes in increasing order.
To determine the minimum number of swaps, consider each level as an array and apply a cycle detection method over it. The size of cycles can determine how many swaps are needed because each cycle in a permutation corresponds to a number of swaps to sort it.
from collections import deque
def minOperations(root):
def BFS_levels(root):
levels = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
if node:
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if current_level:
levels.append(current_level)
return levels
def min_swaps_to_sort(arr):
indexed_arr = list(enumerate(arr))
indexed_arr.sort(key=lambda x: x[1])
visited = {i: False for i in range(len(arr))}
swaps = 0
for i in range(len(arr)):
if visited[i] or indexed_arr[i][0] == i:
continue
cycle_size = 0
j = i
while not visited[j]:
visited[j] = True
j = indexed_arr[j][0]
cycle_size += 1
if cycle_size > 0:
swaps += (cycle_size - 1)
return swaps
levels = BFS_levels(root)
return sum(min_swaps_to_sort(level) for level in levels)import java.util.*;
public class Solution {
public int minOperations(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
levels.add(level);
}
int ops = 0;
for (List<Integer> level : levels) {
ops += minSwaps(level);
}
return ops;
}
private int minSwaps(List<Integer> level) {
int n = level.size();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = level.get(i);
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < n; i++) indexMap.put(arr[i], i);
Arrays.sort(arr);
boolean[] visited = new boolean[n];
int swaps = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || indexMap.get(arr[i]) == i) continue;
int cycleSize = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = indexMap.get(arr[j]);
cycleSize++;
}
if (cycleSize > 0) {
swaps += (cycleSize - 1);
}
}
return swaps;
}
}The solution consists of two main parts:
1. Compute the levels using BFS.
2. For each level, compute the minimum number of swaps required to sort the nodes using a cycle detection method. The sum of these swaps for all levels is the final answer.
Time Complexity: O(n log n), where n is the number of nodes, due to sorting operations per level.
Space Complexity: O(n) to store level arrays and indices.
Approach 2: DFS for Level Order with In-Place Reordering
In this approach, we still traverse the levels of the binary tree using DFS in addition to temporarily capturing the values at each level, then directly modifying the tree nodes to achieve the desired order.
It leverages an in-place sorting strategy to ensure minimal swaps are performed on elements by managing their positions directly at the tree level, albeit with a DFS traversal initially to fetch values.
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function minOperations(root) {
let levels = [];
function dfs(node, depth) {
if (!node) return;
if (depth === levels.length) levels.push([]);
levels[depth].push(node);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
function countSwaps(arr) {
let indexedArr = arr.map((val, index) => [val, index]);
indexedArr.sort((a, b) => a[0] - b[0]);
let visited = Array(arr.length).fill(false);
let numSwaps = 0;
for (let i = 0; i < arr.length; i++) {
if (visited[i] || indexedArr[i][1] === i) continue;
let cycleSize = 0;
let j = i;
while (!visited[j]) {
visited[j] = true;
j = indexedArr[j][1];
cycleSize++;
}
if (cycleSize > 0) numSwaps += (cycleSize - 1);
}
return numSwaps;
}
dfs(root, 0);
let totalSwaps = 0;
for (let i = 0; i < levels.length; i++) {
const levelValues = levels[i].map(node => node.val);
totalSwaps += countSwaps(levelValues);
}
return totalSwaps;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int MinOperations(TreeNode root) {
List<List<TreeNode>> levels = new List<List<TreeNode>>();
void DFS(TreeNode node, int depth) {
if (node == null) return;
if (depth == levels.Count) levels.Add(new List<TreeNode>());
levels[depth].Add(node);
DFS(node.left, depth + 1);
DFS(node.right, depth + 1);
}
DFS(root, 0);
int TotalSwaps(List<TreeNode> level) {
int n = level.Count;
int[] valArray = new int[n];
for (int i = 0; i < n; i++) valArray[i] = level[i].val;
List<int> indices = new List<int>();
for (int i = 0; i < n; i++) indices.Add(i);
indices.Sort((x, y) => valArray[x] - valArray[y]);
bool[] visited = new bool[n];
int swaps = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || indices[i] == i) continue;
int cycleSize = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = indices[j];
cycleSize++;
}
if (cycleSize > 0) swaps += (cycleSize - 1);
}
return swaps;
}
int totalOps = 0;
foreach (var level in levels) {
totalOps += TotalSwaps(level);
}
return totalOps;
}
}The JavaScript solution uses DFS to traverse and collect nodes at each level, then determines the minimum swap count with an index mapping and cycle detection strategy. This helps retain the order directly by working with references to tree nodes.
Time Complexity: O(n log n) due to in-level sorting operations.
Space Complexity: O(n) for capturing all nodes across the tree depths.
Approach 3: BFS + Discretization + Element Swap
First, we traverse the binary tree using BFS to find the node values at each level. Then, we sort the node values at each level. If the sorted node values are different from the original node values, it means that we need to swap elements. The number of swaps is the number of operations needed at that level.
The time complexity is O(n times log n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minimumOperations(TreeNode* root) {
queue<TreeNode*> q{{root}};
int ans = 0;
auto f = [](vector<int>& t) {
int n = t.size();
vector<int> alls(t.begin(), t.end());
sort(alls.begin(), alls.end());
unordered_map<int, int> m;
int ans = 0;
for (int i = 0; i < n; ++i) m[alls[i]] = i;
for (int i = 0; i < n; ++i) t[i] = m[t[i]];
for (int i = 0; i < n; ++i) {
while (t[i] != i) {
swap(t[i], t[t[i]]);
++ans;
}
}
return ans;
};
while (!q.empty()) {
vector<int> t;
for (int n = q.size(); n; --n) {
auto node = q.front();
q.pop();
t.emplace_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans += f(t);
}
return ans;
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minimumOperations(root: TreeNode | null): number {
const queue = [root];
let ans = 0;
while (queue.length !== 0) {
const n = queue.length;
const row: number[] = [];
for (let i = 0; i < n; i++) {
const { val, left, right } = queue.shift();
row.push(val);
left && queue.push(left);
right && queue.push(right);
}
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (row[j] < row[minIdx]) {
minIdx = j;
}
}
if (i !== minIdx) {
[row[i], row[minIdx]] = [row[minIdx], row[i]];
ans++;
}
}
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minimumOperations(root *TreeNode) (ans int) {
f := func(t []int) int {
var alls []int
for _, v := range t {
alls = append(alls, v)
}
sort.Ints(alls)
m := make(map[int]int)
for i, v := range alls {
m[v] = i
}
for i := range t {
t[i] = m[t[i]]
}
res := 0
for i := range t {
for t[i] != i {
t[i], t[t[i]] = t[t[i]], t[i]
res++
}
}
return res
}
q := []*TreeNode{root}
for len(q) > 0 {
t := []int{}
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
t = append(t, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans += f(t)
}
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut queue = VecDeque::new();
queue.push_back(root);
let mut ans = 0;
while !queue.is_empty() {
let n = queue.len();
let mut row = Vec::new();
for _ in 0..n {
let mut node = queue.pop_front().unwrap();
let mut node = node.as_mut().unwrap().borrow_mut();
row.push(node.val);
if node.left.is_some() {
queue.push_back(node.left.take());
}
if node.right.is_some() {
queue.push_back(node.right.take());
}
}
for i in 0..n - 1 {
let mut min_idx = i;
for j in i + 1..n {
if row[j] < row[min_idx] {
min_idx = j;
}
}
if i != min_idx {
row.swap(i, min_idx);
ans += 1;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach with BFS and Cycles | Time Complexity: O(n log n), where n is the number of nodes, due to sorting operations per level. |
| DFS for Level Order with In-Place Reordering | Time Complexity: O(n log n) due to in-level sorting operations. |
| BFS + Discretization + Element Swap | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS + Cycle Detection | O(n log n) | O(n) | Best general solution when processing tree level by level |
| DFS Level Collection + In-Place Reordering | O(n log n) | O(n) | Useful when DFS traversal is already implemented or preferred |
Frequently asked questions
Is Minimum Number of Operations to Sort a Binary Tree by Level easy or hard?
The problem is classified as Medium difficulty. The tree traversal itself is straightforward, but recognizing that each level reduces to a minimum-swaps-to-sort problem requires knowledge of permutation cycles and array sorting techniques.
Minimum Number of Operations to Sort a Binary Tree by Level Python/Java solution
Most implementations follow BFS to gather values per level and then compute minimum swaps using cycle detection. Python solutions typically use lists and sorting with enumerated indices, while Java versions use arrays, ArrayList, and custom pair structures for sorting and cycle counting.
How to solve Minimum Number of Operations to Sort a Binary Tree by Level in O(n)?
A true O(n) solution is generally not feasible because determining the sorted order of each level requires sorting or equivalent comparisons. Most correct solutions run in O(n log n) due to sorting the level arrays. Using cycle detection after sorting ensures the swap count is minimal.
What is the best approach for Minimum Number of Operations to Sort a Binary Tree by Level?
The BFS with cycle detection approach is the most effective. Traverse the tree level by level, collect node values, sort them with original indices, and detect permutation cycles to compute minimum swaps. Each cycle of length k contributes k−1 swaps. This produces the minimum operations while keeping the logic clean and interview friendly.
Is Minimum Number of Operations to Sort a Binary Tree by Level asked at Google/Amazon/Meta?
This problem reflects common interview patterns used by companies like Google, Amazon, and Meta. It combines binary tree traversal with array permutation logic. Variants that require computing minimum swaps to sort arrays or processing trees level-by-level appear frequently in technical interviews.
What data structure is used in Minimum Number of Operations to Sort a Binary Tree by Level?
The solution primarily uses a queue for Breadth-First Search, arrays or lists to store level values, and auxiliary structures for index tracking during sorting. Cycle detection relies on visited arrays or index mapping to compute minimum swaps efficiently.
What is the time complexity of Minimum Number of Operations to Sort a Binary Tree by Level?
The optimal solution runs in O(n log n) time. BFS traversal processes all n nodes, while sorting the values at each level dominates the cost. Across all levels the sorting work totals O(n log n). Space complexity is O(n) for storing level values and auxiliary arrays.