LeetCode Solutions Blog

Minimum Number of Operations to Sort a Binary Tree by Level

Number: 2558

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree with unique values, you can swap the values of any two nodes at the same level. The goal is to determine the minimum number of swaps required so that the values at each level are in strictly increasing order.

Key Insights

The problem naturally breaks down by levels; perform a level-order traversal (BFS) to process each level independently.
For each level, the task reduces to finding the minimum number of adjacent swaps required to sort the array.
The minimum swap count can be computed using cycle detection on the permutation formed by comparing the current level array with its sorted version.
The cycle detection method works by comparing each element’s current position to its correct position and accumulating (cycle length - 1) for each cycle.

Space and Time Complexity

Time Complexity: O(n log n) in the worst-case scenario, where n is the number of nodes. This arises since each level’s array is sorted. Space Complexity: O(n) to store nodes during the BFS traversal.

Solution

We solve the problem by using a breadth-first search to traverse the binary tree level by level. For each level, we extract the node values into an array. To compute the minimum number of operations required to sort this level, we first create a sorted copy of the array to determine the correct positions of values. Then, we map each value to its correct index and find cycles in the permutation. The number of swaps required to fix one cycle is the length of that cycle minus one. Summing up swaps for all levels gives the final result.

The main data structures used are:

A queue for BFS to traverse the binary tree level by level.
An array list for storing values at each level.

The trick here is the cycle detection in the permutation, which avoids using inefficient swapping simulations.

Code Solutions

# 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

from collections import deque

class Solution:
    def minimumOperations(self, root: 'TreeNode') -> int:
        # Initialize total swap count to 0.
        total_swaps = 0
        
        # Use a deque for BFS.
        queue = deque([root])
        
        # Traverse the tree level by level.
        while queue:
            level_length = len(queue)
            level_vals = []
            
            # Collect nodes at the current level and prepare the next level.
            for _ in range(level_length):
                node = queue.popleft()
                level_vals.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Compute minimum swaps for current level by cycle detection.
            total_swaps += self._min_swaps(level_vals)
        
        return total_swaps
    
    def _min_swaps(self, nums):
        # Create a list of tuples where each tuple is (value, original_index).
        n = len(nums)
        # Sorted order of values along with their original indices.
        arr = sorted([(val, i) for i, val in enumerate(nums)])
        
        visited = [False] * n
        swaps = 0
        
        # Iterate over each element for cycle detection.
        for i in range(n):
            # Skip if element is already visited or in correct position.
            if visited[i] or arr[i][1] == i:
                continue
            
            cycle_size = 0
            j = i
            
            # Follow the cycle.
            while not visited[j]:
                visited[j] = True
                # Move to the index where the element should be.
                j = arr[j][1]
                cycle_size += 1
            
            # If there is a cycle, add (cycle_size - 1) to swaps.
            if cycle_size > 0:
                swaps += (cycle_size - 1)
        
        return swaps