#2471

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Minimum Number of Operations to Sort a Binary Tree by Level

Determine the minimum number of swaps to sort each level of a binary tree using level-wise traversal efficiently.

Problem Statement

You are given the root of a binary tree where each node has a unique value. At each level of the tree, you can perform an operation that swaps the values of any two nodes at that level. Determine the fewest number of such operations required to make every level of the tree sorted in strictly increasing order.

Implement a function that traverses the binary tree level by level, identifies the order of values at each level, and returns the total minimum number of swaps needed across all levels. Each level is considered independently, and only swaps among nodes on the same level are allowed.

Examples

Example 1

Input: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]

Output: 3

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

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

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.

Solution Approach

Level Order Traversal

Perform a breadth-first search to collect all node values at each level. Store each level as a separate list so that the sorting operations can be applied independently.

Calculate Minimum Swaps per Level

For each level, determine the minimum number of swaps required to sort the values in strictly increasing order. This can be done by mapping current indices to target positions and counting cycles.

Aggregate Results Across Levels

Sum the minimum swaps computed for each level to get the total number of operations. Return this sum as the final result, ensuring that each level is independently sorted in the minimum steps.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Time complexity is O(n log n) due to sorting each level during minimum swap computation, and space complexity is O(n) for storing values of all levels during BFS traversal.

What Interviewers Usually Probe

Does your solution correctly handle large binary trees with up to 105 nodes?
Can you explain how you calculate minimum swaps for a single level efficiently?
Have you considered that swaps are only allowed between nodes on the same level?

Common Pitfalls or Variants

Common pitfalls

Trying to swap nodes across different levels instead of handling levels independently.
Forgetting that node values are unique, which affects the cycle counting in minimum swap computation.
Not using BFS and incorrectly mixing depth-first approaches that complicate level tracking.

Follow-up variants

Compute minimum operations when duplicate values are allowed, requiring value frequency tracking.
Determine minimum swaps to sort levels in non-strictly increasing order, modifying the target sequence criteria.
Optimize for very wide binary trees where storing entire levels might need streaming or partial storage.

FAQ

What is the best way to traverse the binary tree for this problem?

Use breadth-first search to collect values level by level, as each level is sorted independently for minimum swaps.

How do I calculate the minimum number of swaps for a level?

Map each value to its target index in sorted order and count cycles; the total swaps are sum(cycle_length - 1) for all cycles.

Does the tree need to be balanced for this approach?

No, the solution works for any binary tree structure because it handles each level separately regardless of balance.

Can I swap nodes across different levels?

No, swaps are restricted to nodes on the same level; inter-level swaps are not allowed in this problem.

Why is this called 'Binary-tree traversal and state tracking' pattern?

Because the solution relies on BFS traversal to track the state of each level independently, which is central to computing minimum operations.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        def swap(arr, i, j):
            arr[i], arr[j] = arr[j], arr[i]

        def f(t):
            n = len(t)
            m = {v: i for i, v in enumerate(sorted(t))}
            for i in range(n):
                t[i] = m[t[i]]
            ans = 0
            for i in range(n):
                while t[i] != i:
                    swap(t, i, t[i])
                    ans += 1
            return ans

        q = deque([root])
        ans = 0
        while q:
            t = []
            for _ in range(len(q)):
                node = q.popleft()
                t.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans += f(t)
        return ans

Continue Practicing

#2458 height of binary tree after subtree removal queries #2415 reverse odd levels of binary tree #2385 amount of time for binary tree to be infected