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:
[1, 105].1 <= Node.val <= 105Problem 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.
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.
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.
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.
JavaScript
C#
Time Complexity: O(n log n) due to in-level sorting operations.
Space Complexity: O(n) for capturing all nodes across the tree depths.
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.
| 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 | — |
| 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 |
Minimum Number of Operations to Sort a Binary Tree by Level - Leetcode 2471 - Python • NeetCodeIO • 8,451 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Sort a Binary Tree by Level with our built-in code editor and test cases.
Practice on FleetCode