Problem

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 astrictly increasing order.

The level of a node is the number of edges along the path between it and the root node.

Examples

Example 1:

 graph TD;
     A[1]
     B[4]
     C[3]
     D[7]
     E[6]
     F[8]
     G[5]
     H[9]
     I[10]
 
     A --> B & C
     B --> D & E
     C --> F & G
     F --> H
     F ~~~ N1:::hidden
     G --> I
     G ~~~ N2:::hidden

classDef hidden display: none;
  
1
2
3
4
5
6
7
8

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:

graph TD;
    A[1]
    B[3]
    C[2]
    D[7]
    E[6]
    F[5]
    G[4]

    A --> B & C
    B --> D & E
    C --> F & G
  
1
2
3
4
5
6
7
8

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:

graph TD;
    A[1]
    B[2]
    C[3]
    D[4]
    E[5]
    F[6]

    A --> B & C
    B --> D & E
    C --> F
    C ~~~ N1:::hidden

classDef hidden display: none;
  
1
2
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, 10^5].
  • 1 <= Node.val <= 105
  • All the values of the tree are unique.

Solution

Method 1 - BFS + Cycle Sort

Here is the approach:

  1. Level Order Traversal: First, traverse the tree level by level using BFS (Breadth-First Search). This is what we covered at Binary Tree Level Order Traversal - Level by Level.
  2. Sorting with Minimum Swaps: For each level of nodes, determine the minimum number of swaps needed to sort the nodes in strictly increasing order. This can be efficiently determined using the concept of cycle decomposition from graph theory.
    1. Cycle sort is a technique used to address problems requiring a minimum number of swaps or finding missing numbers within a given range. Using cycle sort allows us to efficiently compute the minimum swaps needed to sort the values at each level in strictly increasing order.

Code

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class Solution {
    public int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int ans = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ans += minSwaps(level);
        }
        
        return ans;
    }

    private int minSwaps(List<Integer> arr) {
        int n = arr.size();
        int[] arrPos = new int[n];
        for (int i = 0; i < n; i++) {
            arrPos[i] = i;
        }
        arrPos = Arrays.stream(arrPos).boxed()
            .sorted(Comparator.comparingInt(arr::get))
            .mapToInt(Integer::intValue)
            .toArray();
        
        boolean[] visited = new boolean[n];
        int ans = 0;
        
        for (int i = 0; i < n; i++) {
            if (visited[i] || arrPos[i] == i)
                continue;
            int cycleSize = 0;
            int x = i;
            while (!visited[x]) {
                visited[x] = true;
                x = arrPos[x];
                cycleSize++;
            }
            if (cycleSize > 0) {
                ans += (cycleSize - 1);
            }
        }
        return ans;
    }
}
 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
37
38
39

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        ans = 0
        queue = deque([root])
        
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans += self.minSwaps(level)
        
        return ans

    def minSwaps(self, arr: List[int]) -> int:
        n = len(arr)
        arr_pos = sorted(range(n), key=lambda x: arr[x])
        visited = [False] * n
        ans = 0
        
        for i in range(n):
            if visited[i] or arr_pos[i] == i:
                continue
            cycle_size = 0
            x = i
            while not visited[x]:
                visited[x] = True
                x = arr_pos[x]
                cycle_size += 1
            if cycle_size > 0:
                ans += (cycle_size - 1)
        return ans

Complexity

  • ⏰ Time complexity: O(n log n) where n is the number of nodes in the binary tree. This includes O(n) for level order traversal and O(n log n) for sorting and calculating minimum swaps.
  • 🧺 Space complexity: O(n) to store the nodes at each level during the traversal.

Method 2 - BFS + Greedily count min swaps

The trick is to count the number of swaps needed by obtaining the array of numbers at a particular level using BFS traversal. To calculate the count in linear complexity, we need extra space. We store the level array in an ordered map with indices as values and copy it to a secondary array “sorted”. We then sort “sorted” to find the correct indices of each element. Next, we traverse the original level array “arr” and check if its values are at the correct indices when sorted. If not, we get the original index from the map and swap the elements, gradually sorting the “arr” array.

Here is the approach:

  1. Level Order Traversal: Traverse the tree level by level using BFS to get the array of node values at each level.
  2. Sorting with Minimum Swaps (Using HashMap):
    • Use extra space to handle the node values efficiently.
    • Add the level array to an ordered map with indices as values and also copy it to a secondary array (sorted).
    • Sort the secondary array to get the correct indices of each element.
    • Traverse the original level array (arr) and check if its values are at the correct indices as per the sorted array.
    • If not at the correct position, get the original index from the map and swap the elements to gradually sort the original array.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
    public int minimumOperations(TreeNode root) {        
        int ans = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ans += minSwaps(level);
        }
        
        return ans;
    }

    private int minSwaps(List<Integer> arr) {
        int n = arr.size();
        Map<Integer, Integer> numToIdxMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            numToIdxMap.put(arr.get(i), i);
        }
        
        List<Integer> sorted = new ArrayList<>(arr);
        Collections.sort(sorted);
        
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            if (!arr.get(i).equals(sorted.get(i))) {
                swaps++;
                
                int a = arr.get(i);
                int b = sorted.get(i);
                
                // Swap the values
                arr.set(numToIdxMap.get(b), a);
                numToIdxMap.put(a, numToIdxMap.get(b));
                
                arr.set(i, b);
                numToIdxMap.put(b, i);
            }
        }
        return swaps;
    }
}
 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
37
38
39
40
41
42
43
44
45
46

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        ans = 0
        queue = deque([root])
        
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans += self.minSwaps(level)
        
        return ans

    def minSwaps(self, arr: List[int]) -> int:
        n = len(arr)
        numToIdxMap = {}
        for i in range(n):
            numToIdxMap[arr[i]] = i
        
        sorted_lst = list(arr)
        sorted_lst.sort()
        
        swaps = 0
        for i in range(n):
            if arr[i] != sorted_lst[i]:
                swaps += 1
                
                a = arr[i]
                b = sorted_lst[i]
                
                # Swap the values
                arr[numToIdxMap[b]] = a
                numToIdxMap[a] = numToIdxMap[b]
                
                arr[i] = b
                numToIdxMap[b] = i
        
        return swaps

Complexity

  • ⏰ Time complexity: O(n log n) where n is the number of nodes in the binary tree. This includes O(n) for level order traversal and O(n log n) for sorting and calculating minimum swaps.
  • 🧺 Space complexity: O(n) to store the nodes at each level during the traversal.