Minimum Number of Operations to Sort a Binary Tree by Level

Med

#2255Time: O(N^2) in the worst case. The level order traversal itself takes O(N) time, where N is the total number of nodes. For each level with `k` nodes, the `countSwaps` function, which implements Selection Sort, takes O(k^2) time. In a complete binary tree, the last level can have about N/2 nodes, making the complexity for that single level O((N/2)^2) = O(N^2). This dominates the overall time complexity.Space: O(W), where W is the maximum width of the binary tree. This space is required for the BFS queue and the list to store the values of the nodes at a single level. In the worst case of a complete binary tree, W can be proportional to N, making the space complexity O(N).1 company

Algorithms

Breadth-First Search

Data structures

Tree Binary Tree

Companies

Guidewire

Prompt

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:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁵
All the values of the tree are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach processes the tree level by level using Breadth-First Search (BFS). For each level, it collects all node values into a list. Then, it calculates the minimum swaps required to sort this list using a method analogous to Selection Sort. The number of swaps performed by Selection Sort is known to be the minimum required to sort an array. The total number of operations is the sum of swaps required for each level.

Algorithm

Initialize total_swaps = 0.
If the root is null, return 0.
Create a queue for Level Order Traversal and add the root node.
Loop while the queue is not empty:
- Determine the number of nodes at the current level, level_size.
- Create a list, level_values, to store the values of nodes at this level.
- Dequeue level_size nodes. For each node, add its value to level_values and enqueue its non-null children.
- Calculate the number of swaps needed to sort level_values using a Selection Sort-like process:
  - Initialize level_swaps = 0.
  - Iterate with index i from 0 to the second to last element of level_values.
  - In each iteration, find the index min_idx of the smallest element in the sublist starting from i.
  - If min_idx is not equal to i, it means the element at i is not the smallest possible. Swap the elements at i and min_idx, and increment level_swaps.
- Add level_swaps to total_swaps.
Return total_swaps.

Walkthrough

The algorithm begins with a standard level order traversal using a queue. In each step of the traversal, we process all nodes at the current level. The values of these nodes are collected into a temporary list. To find the minimum number of swaps for this list, we apply the logic of Selection Sort. We iterate through the list from left to right. For each position i, we find the smallest element in the rest of the list (from i to the end). If this smallest element is not already at position i, we swap it into place and count it as one operation. This process is repeated for every level, and the swap counts from each level are summed up to get the final result.

1class Solution {2    public int minimumOperations(TreeNode root) {3        if (root == null) {4            return 0;5        }6 7        int operations = 0;8        Queue<TreeNode> queue = new LinkedList<>();9        queue.offer(root);10 11        while (!queue.isEmpty()) {12            int levelSize = queue.size();13            List<Integer> levelValues = new ArrayList<>();14            for (int i = 0; i < levelSize; i++) {15                TreeNode node = queue.poll();16                levelValues.add(node.val);17                if (node.left != null) {18                    queue.offer(node.left);19                }20                if (node.right != null) {21                    queue.offer(node.right);22                }23            }24            operations += countSwaps(levelValues);25        }26        return operations;27    }28 29    // Counts swaps using Selection Sort logic30    private int countSwaps(List<Integer> arr) {31        int n = arr.size();32        int swaps = 0;33        for (int i = 0; i < n - 1; i++) {34            int minIndex = i;35            for (int j = i + 1; j < n; j++) {36                if (arr.get(j) < arr.get(minIndex)) {37                    minIndex = j;38                }39            }40            if (minIndex != i) {41                Collections.swap(arr, i, minIndex);42                swaps++;43            }44        }45        return swaps;46    }47}

Complexity

Time

O(N^2) in the worst case. The level order traversal itself takes O(N) time, where N is the total number of nodes. For each level with `k` nodes, the `countSwaps` function, which implements Selection Sort, takes O(k^2) time. In a complete binary tree, the last level can have about N/2 nodes, making the complexity for that single level O((N/2)^2) = O(N^2). This dominates the overall time complexity.

Space

O(W), where W is the maximum width of the binary tree. This space is required for the BFS queue and the list to store the values of the nodes at a single level. In the worst case of a complete binary tree, W can be proportional to N, making the space complexity O(N).

Trade-offs

Pros

The approach is straightforward and relatively easy to understand and implement.
It correctly breaks down the problem into independent subproblems for each level.

Cons

The time complexity for sorting each level is O(k^2), where k is the number of nodes at that level. This can lead to an overall time complexity of O(N^2) for a balanced tree, which is inefficient and may time out on larger test cases.

This optimized approach also uses BFS to process the tree level by level. However, it employs a more efficient algorithm to count the minimum swaps for each level's values. The problem of finding the minimum swaps to sort an array is equivalent to finding the number of cycles in its permutation. The minimum number of swaps is k - C, where k is the number of elements and C is the number of cycles. This can be implemented efficiently by creating a sorted version of the level's values and using a hash map to track the positions of elements, bringing them to their correct sorted positions one by one.

Algorithm

Initialize total_swaps = 0.
If the root is null, return 0.
Create a queue for Level Order Traversal and add the root node.
Loop while the queue is not empty:
- Determine the number of nodes at the current level, level_size.
- Create a list, level_values, to store the values of nodes at this level.
- Dequeue level_size nodes, add their values to level_values, and enqueue their children.
- Calculate swaps for level_values (of size k) using a cycle sort approach:
  - Create a sorted copy of the list, sorted_values.
  - Create a HashMap val_to_idx to map each value in level_values to its current index.
  - Initialize level_swaps = 0.
  - Iterate with index i from 0 to k-1:
    - If the value at level_values[i] is not the same as sorted_values[i], it means the element is misplaced.
    - Increment level_swaps.
    - Identify the current_val at level_values[i] and the correct_val that should be at this position (sorted_values[i]).
    - Find the index of correct_val using the val_to_idx map.
    - Swap the elements in level_values.
    - Update the val_to_idx map for the two values that were swapped.
- Add level_swaps to total_swaps.
Return total_swaps.

Walkthrough

The algorithm traverses the tree using BFS. For each level, it gathers the node values into a list level_values. To find the minimum swaps for this list of size k, we first create a sorted copy, sorted_values, to know the target state. We also use a HashMap to store the current index of each value, allowing for O(1) lookups.

We then iterate from i = 0 to k-1. If the element at level_values.get(i) is not what it should be (i.e., not equal to sorted_values.get(i)), we know a swap is necessary. We find the element that should be at index i (which is sorted_values.get(i)) and swap it with the current element. The hash map is used to quickly find the index of the element we need to swap with. After each swap, we update the hash map to reflect the new positions of the swapped elements. The total count of such swaps gives the minimum for that level.

1class Solution {2    public int minimumOperations(TreeNode root) {3        if (root == null) {4            return 0;5        }6 7        int operations = 0;8        Queue<TreeNode> queue = new LinkedList<>();9        queue.offer(root);10 11        while (!queue.isEmpty()) {12            int levelSize = queue.size();13            List<Integer> levelValues = new ArrayList<>();14            for (int i = 0; i < levelSize; i++) {15                TreeNode node = queue.poll();16                levelValues.add(node.val);17                if (node.left != null) {18                    queue.offer(node.left);19                }20                if (node.right != null) {21                    queue.offer(node.right);22                }23            }24            operations += countSwaps(levelValues);25        }26        return operations;27    }28 29    private int countSwaps(List<Integer> arr) {30        int n = arr.size();31        if (n <= 1) {32            return 0;33        }34 35        List<Integer> sortedArr = new ArrayList<>(arr);36        Collections.sort(sortedArr);37 38        Map<Integer, Integer> valToIndex = new HashMap<>();39        for (int i = 0; i < n; i++) {40            valToIndex.put(arr.get(i), i);41        }42 43        int swaps = 0;44        for (int i = 0; i < n; i++) {45            if (!arr.get(i).equals(sortedArr.get(i))) {46                swaps++;47                int val1 = arr.get(i);48                int val2 = sortedArr.get(i);49 50                int index2 = valToIndex.get(val2);51 52                // Swap in the array53                arr.set(i, val2);54                arr.set(index2, val1);55 56                // Update map for the two swapped values57                valToIndex.put(val1, index2);58                valToIndex.put(val2, i);59            }60        }61        return swaps;62    }63}

Complexity

Time

O(N log N). The BFS traversal takes O(N). For each level with `k` nodes, the dominant operation is sorting the list of values, which takes O(k log k). The sum of `k_i * log(k_i)` over all levels `i` (where `sum(k_i) = N`) is bounded by O(N log N). The subsequent swapping loop takes O(k) time per level. Thus, the total time complexity is O(N log N).

Space

O(W), where W is the maximum width of the tree. This space is used for the BFS queue, the list for level values, its sorted copy, and the hash map. In the worst case of a complete binary tree, W can be O(N).

Trade-offs

Pros

Highly efficient, with a time complexity that can handle large inputs.
It is guaranteed to find the minimum number of swaps based on the cycle decomposition of permutations.

Cons

The implementation is more complex than the naive selection sort approach, requiring extra space for a sorted copy and a hash map.
Requires careful management of values and their indices during the swapping process.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int minimumOperations ( TreeNode root ) { Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); int ans = 0 ; while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } ans += f ( t ); } return ans ; } private int f ( List < Integer > t ) { int n = t . size (); List < Integer > alls = new ArrayList <>( t ); alls . sort (( a , b ) -> a - b ); Map < Integer , Integer > m = new HashMap <>(); for ( int i = 0 ; i < n ; ++ i ) { m . put ( alls . get ( i ), i ); } int [] arr = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { arr [ i ] = m . get ( t . get ( i )); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { while ( arr [ i ] != i ) { swap ( arr , i , arr [ i ]); ++ ans ; } } return ans ; } private void swap ( int [] arr , int i , int j ) { int t = arr [ i ]; arr [ i ] = arr [ j ]; arr [ j ] = t ; } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int minimumOperations ( TreeNode * root ) { queue < TreeNode *> q { { root } }; int ans = 0 ; auto f = []( vector < int >& t ) { int n = t . size (); vector < int > alls ( t . begin (), t . end ()); sort ( alls . begin (), alls . end ()); unordered_map < int , int > m ; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) m [ alls [ i ]] = i ; for ( int i = 0 ; i < n ; ++ i ) t [ i ] = m [ t [ i ]]; for ( int i = 0 ; i < n ; ++ i ) { while ( t [ i ] != i ) { swap ( t [ i ], t [ t [ i ]]); ++ ans ; } } return ans ; }; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n ; -- n ) { auto node = q . front (); q . pop (); t . emplace_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans += f ( t ); } return ans ; } };

1# 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem