LeetCode Solutions Blog

Minimum Number of Operations to Sort a Binary Tree by Level

Difficulty: Medium

Problem Description

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.

Key Insights

Each level of the binary tree can be treated separately.
To determine the number of swaps required to sort each level, we can use the concept of cycles in permutations.
The number of swaps needed to sort an array can be derived from the number of cycles in the corresponding permutation of indices.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the binary tree, as we need to traverse all nodes. Space Complexity: O(N) - for storing the values at each level.

Solution

We utilize a breadth-first search (BFS) to traverse the binary tree level by level. For each level, we collect the node values and their corresponding indices. We then determine the number of swaps needed to sort these values by analyzing the cycles in the index permutation. By counting the cycles, we can compute the minimum number of swaps required to sort the level.

Code Solutions

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minimumOperations(root: TreeNode) -> int:
    if not root:
        return 0

    level_values = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        level_values.append(current_level)

    total_swaps = 0

    for level in level_values:
        sorted_level = sorted(level)
        index_map = {value: i for i, value in enumerate(level)}
        visited = [False] * len(level)

        for i in range(len(level)):
            if visited[i] or sorted_level[i] == level[i]:
                continue
            
            cycle_size = 0
            while not visited[i]:
                visited[i] = True
                i = index_map[sorted_level[i]]
                cycle_size += 1
            
            if cycle_size > 0:
                total_swaps += (cycle_size - 1)

    return total_swaps