Minimum Number of Operations to Sort a Binary Tree by Level - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
Code
JavaScript
C#
Complexity
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.
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 | — |
Detailed 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 |
Video Solution
Minimum Number of Operations to Sort a Binary Tree by Level | Leetcode 2471 | codestorywithMIK • codestorywithMIK • 8,797 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Operations to Sort a Binary Tree by Level easy or hard?
Minimum Number of Operations to Sort a Binary Tree by Level Python/Java solution
How to solve Minimum Number of Operations to Sort a Binary Tree by Level in O(n)?
What is the best approach for Minimum Number of Operations to Sort a Binary Tree by Level?
Is Minimum Number of Operations to Sort a Binary Tree by Level asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Operations to Sort a Binary Tree by Level?
What is the time complexity of Minimum Number of Operations to Sort a Binary Tree by Level?
Ready to solve this problem?
Practice Minimum Number of Operations to Sort a Binary Tree by Level with our built-in code editor and test cases.
Practice on FleetCode