2471. Minimum Number of Operations to Sort a Binary Tree by Level

MediumTreeBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

In this problem, we're working with a binary tree where each node has a unique value. Our objective is to sort the values on each level of the tree in strictly increasing order. We have an operation at our disposal where we can swap the values of any two nodes at the same level. The challenge is to figure out the minimum number of such operations required to achieve the sorting.

To better understand, let's visualize the binary tree as a hierarchical structure with the root at the top. Each level below the root contains a set of nodes that are directly connected above. We are looking to sort the nodes at each horizontal level without altering the tree's structure; only the node values are swapped.

The complexity arises because we must do this by swapping node values within the same level. Nodes belonging to different levels cannot have their values exchanged. The goal is to perform this task using the smallest possible number of swaps.

Intuition

For the solution, we consider each level of the tree separately. We need to solve the sorting problem level by level instead of looking at the tree as a whole. Because the tree nodes at the same level can be treated as an array, if we had these nodes in an array, we could then sort this array with a minimal number of swaps.

The concept the solution relies on is very similar to finding the number of swaps needed to sort an array. It can be solved by utilizing the cycle decomposition approach for permutation sorting, which gives us the number of swaps needed to arrange the numbers in increasing order if each number can only be in the position denoted by its value.

Here's our approach in steps:

  1. Traverse the tree level by level, using a queue to keep track of nodes.
  2. For each level, collect the values of the nodes.
  3. Sort these values to get the target position for each value.
  4. Use the sorted values to map each original node value to its target position.
  5. Count the number of swaps by using cycle decomposition, where we cycle through the indices until each element is in its correct position.
  6. Add up the swap counts for each level to get the total minimum number of swaps needed for the entire tree.

In the implementation, function f(t) is responsible for counting the swaps required to sort a given array t. The main section of the code traverses the tree and for each level, uses f(t) to count the necessary swaps, then sums them up in the ans variable, which is returned as the final answer.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The provided solution capitalizes on the properties of tree traversal and permutation sorting. Here's the breakdown based on the given Python code:

Data Structures Used:

  • A Queue (deque): It's employed to assist in level-order traversal of the tree.
  • A List/Array: To hold node values at a given level.
  • A Dictionary/Map: To track the target position of each value after sorting.

Algorithm and Patterns:

The Queue for Level-order Traversal: Level-order traversal visits all nodes in the tree level by level, which is crucial for our task since we can only swap nodes at the same level.

  1. Initialize a queue and enqueue the root node.
  2. Loop until the queue is empty:
    • Initialize an empty list t for the current level.
    • Dequeue nodes of the current level, add their values to t and enqueue their children (if any).
    • After the loop, all values of the current level are in t.

Sorting and Mapping: We need to determine the original position and target position for node values.

  1. Sort the list t and use the sorted list to create a mapping where each original value points to its corresponding index in the sorted list. This step effectively provides us with the final sorted positions of the node values.

Counting Swaps Using Cycle Decomposition: Cycle decomposition is a way to find out how many swaps are needed to sort a permutation. Each cycle can be sorted with a number of swaps equal to the size of the cycle minus one.

  1. Iterate through t and keep swapping each element until it reaches its correct position according to the mapping. Increment the ans counter each time a swap is performed.
    • The function swap(arr, i, j) is a helper that swaps elements i and j in arr.
    • The function f(t) is the implementation of the cycle decomposition algorithm applied to the values at the current level (stored in t). It returns the number of swaps needed to sort t.

Putting It All Together:

  1. The main function minimumOperations utilizes the queue to go through the tree level by level and keeps an overall counter ans to accumulate the swaps.
  2. For each level, it collects the node values, sorts them, finds the amount of swaps needed using f(t), and adds that to ans.
    • This is repeated until all levels are processed.
  3. Once all levels have been visited, ans holds the total minimum number of operations required, which is then returned.

Complexity Analysis:

  • Let n be the number of nodes in the binary tree.
  • Time Complexity: O(n log n) due to sorting at every level.
  • Space Complexity: O(n) for storing node values, their mapping, and the queue.

Implementation of the Key Functions:

  • swap(arr, i, j): Swaps the elements at indices i and j in arr.
  • f(t): Applies the cycle decomposition method to count swaps needed to sort t, which represents a single level's values.
  • minimumOperations(root): Initiates the process, looping through each level of the tree, and accumulates the total number of operations.

The combination of level-order traversal and cycles decomposition for permutation sorting is what powers this solution, culminating in the effective sorting of node values at each level of the binary tree with the minimum number of swaps.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the following binary tree, and imagine the goal is to sort the values at each level:

1       4
2      / \
3     3   2
4    / \ 
5   5   1

Starting at the root level, since there is just one node, no operations are needed.

At the second level, there are two nodes with values 3 and 2. To sort these, we need one swap operation to get [2, 3].

At the third level, the two nodes have values 5 and 1. One swap is required to get them in order [1, 5].

Here are the steps according to the solution approach:

  1. Level-order traversal: We place the root node in a queue. We then dequeue it and enqueue its children (3 and 2), making a list of the node values at this level [3, 2].

  2. Sorting and mapping: We sort the array [3, 2] to get [2, 3] and make a note that 3 has to move one position to the left and 2 has to move one position to the right.

  3. Counting swaps using cycle decomposition: To sort the array [3, 2], we swap 3 and 2. We also mark them as visited so that we don't swap them again. This takes 1 swap.

  4. Repeat the process for the next level: For the next level, we enqueue nodes 5 and 1 and make an array [5, 1]. After sorting, we get [1, 5] and determine that 5 has to move one position to the right and 1 one position to the left.

  5. Counting swaps using cycle decomposition: Swapping values 5 and 1 to sort them requires 1 swap.

  6. Accumulate the total swaps: We add the swaps from step 3 (1 swap) and step 5 (1 swap) to get a total of 2 swap operations for the tree.

Thus, the minimum number of operations required to sort the values on each level of the given binary tree is 2.

Solution Implementation

1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def minimumOperations(self, root: Optional[TreeNode]) -> int:
12        # Function to swap elements in an array
13        def swap_elements(array, i, j):
14            array[i], array[j] = array[j], array[i]
15
16        # Function to find the minimum number of swaps needed
17        # to sort the array
18        def find_min_swaps_to_sort(array):
19            length = len(array)
20            # Create a mapping from value to its index after sort
21            value_to_index = {value: index for index, value in enumerate(sorted(array))}
22            # Replace each value with its index after sort
23            for i in range(length):
24                array[i] = value_to_index[array[i]]
25            swaps = 0
26            # Iterate through the array, swapping elements until
27            # the current index matches the sorted index
28            for i in range(length):
29                while array[i] != i:
30                    swap_elements(array, i, array[i])
31                    swaps += 1
32            return swaps
33
34        # Start with a queue containing the root node
35        queue = deque([root])
36        total_swaps = 0
37        # Perform breadth-first traversal of the tree
38        while queue:
39            current_level = []
40            # Process all nodes at the current level
41            for _ in range(len(queue)):
42                node = queue.popleft()
43                # Add the node's value to the current level array
44                current_level.append(node.val)
45                # Add left and right children to queue if they exist
46                if node.left:
47                    queue.append(node.left)
48                if node.right:
49                    queue.append(node.right)
50            # For each level, add the number of swaps needed to sort
51            # the level's values to the total number of swaps
52            total_swaps += find_min_swaps_to_sort(current_level)
53      
54        # Return the total number of swaps required for the whole tree
55        return total_swaps
56
1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    TreeNode() {}
8
9    TreeNode(int val) { this.val = val; }
10
11    TreeNode(int val, TreeNode left, TreeNode right) {
12        this.val = val;
13        this.left = left;
14        this.right = right;
15    }
16}
17
18class Solution {
19    public int minimumOperations(TreeNode root) {
20        Deque<TreeNode> queue = new ArrayDeque<>();
21        queue.offer(root);
22        int operations = 0;
23      
24        // BFS traversal of the tree
25        while (!queue.isEmpty()) {
26            List<Integer> levelValues = new ArrayList<>();
27          
28            // Process all nodes at the current level
29            for (int nodeCount = queue.size(); nodeCount > 0; --nodeCount) {
30                TreeNode currentNode = queue.poll();
31                levelValues.add(currentNode.val);
32              
33                // Add the children of the current node to the queue, if they exist
34                if (currentNode.left != null) {
35                    queue.offer(currentNode.left);
36                }
37                if (currentNode.right != null) {
38                    queue.offer(currentNode.right);
39                }
40            }
41          
42            // Compute the number of operations needed for this level
43            operations += computeOperations(levelValues);
44        }
45      
46        return operations;
47    }
48
49    private int computeOperations(List<Integer> levelValues) {
50        int size = levelValues.size();
51        List<Integer> sortedValues = new ArrayList<>(levelValues);
52        sortedValues.sort(Integer::compareTo);
53        Map<Integer, Integer> valueToIndexMap = new HashMap<>();
54      
55        // Map each value to its index in the sorted list
56        for (int i = 0; i < size; ++i) {
57            valueToIndexMap.put(sortedValues.get(i), i);
58        }
59      
60        // Create an array where each element's value is its index in the sorted list
61        int[] indices = new int[size];
62        for (int i = 0; i < size; ++i) {
63            indices[i] = valueToIndexMap.get(levelValues.get(i));
64        }
65      
66        // Count the number of swaps needed to sort the array
67        int swapCount = 0;
68        for (int i = 0; i < size; ++i) {
69            while (indices[i] != i) {
70                swap(indices, i, indices[i]);
71                ++swapCount;
72            }
73        }
74      
75        return swapCount;
76    }
77
78    // Helper method to swap two elements in an array
79    private void swap(int[] arr, int i, int j) {
80        int temp = arr[i];
81        arr[i] = arr[j];
82        arr[j] = temp;
83    }
84}
85
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
9 * };
10 */
11
12class Solution {
13public:
14    int minimumOperations(TreeNode* root) {
15        // Create a queue for level order traversal.
16        queue<TreeNode*> nodeQueue;
17        nodeQueue.push(root);
18        int totalOperations = 0;
19
20        // Lambda function to calculate minimum operations for each level.
21        auto calculateOperations = [](vector<int>& values) {
22            int size = values.size();
23            vector<int> sortedValues(values.begin(), values.end());
24            sort(sortedValues.begin(), sortedValues.end());
25            unordered_map<int, int> valueToIndexMap;
26            int operationsCount = 0;
27            for (int i = 0; i < size; ++i) {
28                valueToIndexMap[sortedValues[i]] = i;
29            }
30
31            // Calculate operations to sort the values array.
32            for (int i = 0; i < size; ++i) {
33                values[i] = valueToIndexMap[values[i]];
34                while (values[i] != i) {
35                    swap(values[i], values[values[i]]);
36                    ++operationsCount;
37                }
38            }
39            return operationsCount;
40        };
41
42        // Perform level order traversal of the binary tree.
43        while (!nodeQueue.empty()) {
44            vector<int> currentLevelValues;
45            for (int n = nodeQueue.size(); n > 0; --n) {
46                TreeNode* currentNode = nodeQueue.front();
47                nodeQueue.pop();
48                currentLevelValues.push_back(currentNode->val);
49                if (currentNode->left) {
50                    nodeQueue.push(currentNode->left);
51                }
52                if (currentNode->right) {
53                    nodeQueue.push(currentNode->right);
54                }
55            }
56            // Add the operations for the current level to the total.
57            totalOperations += calculateOperations(currentLevelValues);
58        }
59        return totalOperations;
60    }
61};
62
1// Function to calculate the minimum number of operations needed
2// to sort the binary tree by levels from the smallest to the
3// largest value.
4// @param {TreeNode | null} root - The root of the binary tree.
5// @returns The minimum number of operations required.
6function minimumOperations(root: TreeNode | null): number {
7  
8    // Queue to hold the nodes for level-order traversal.
9    const nodeQueue: Array<TreeNode | null> = [root];
10  
11    // Counter to keep track of the number of operations performed.
12    let operationsCount = 0;
13  
14    // Iterating over the tree using level-order traversal.
15    while (nodeQueue.length !== 0) {
16        // Number of nodes at the current level.
17        const levelNodeCount = nodeQueue.length;
18      
19        // Array to store the values of the nodes at the current level
20        // for sorting purposes.
21        const currentLevelValues: number[] = [];
22      
23        // Extracting all nodes at the current level.
24        for (let i = 0; i < levelNodeCount; i++) {
25            const currentNode = nodeQueue.shift();
26            if (currentNode !== null) {
27                // Store the current node's value.
28                currentLevelValues.push(currentNode.val);
29                // Queue the left and right children if they are not null.
30                if (currentNode.left !== null) {
31                    nodeQueue.push(currentNode.left);
32                }
33                if (currentNode.right !== null) {
34                    nodeQueue.push(currentNode.right);
35                }
36            }
37        }
38      
39        // Performing selection sort on the current level's values.
40        for (let i = 0; i < levelNodeCount - 1; i++) {
41            // Assuming the minimum value is at the current index.
42            let minIndex = i;
43            // Finding the actual minimum value's index.
44            for (let j = i + 1; j < levelNodeCount; j++) {
45                if (currentLevelValues[j] < currentLevelValues[minIndex]) {
46                    minIndex = j;
47                }
48            }
49            // If the assumed minimum value's index is not the actual minimum,
50            // swap them and count the operation.
51            if (i !== minIndex) {
52                [currentLevelValues[i], currentLevelValues[minIndex]] = [currentLevelValues[minIndex], currentLevelValues[i]];
53                operationsCount++;
54            }
55        }
56    }
57    // Return the total number of operations performed after
58    // sorting all levels.
59    return operationsCount;
60}
61
Not Sure What to Study? Take the 2-min Quiz๏ผš

A heap is a ...?

Time and Space Complexity

Time Complexity

The given Python function minimumOperations traverses a binary tree and performs operations to calculate the minimum swaps needed to make each level of the tree sorted.

Let n be the total number of nodes in the tree.

  • The function uses a breadth-first search (BFS) approach to traverse the tree level by level. The outer while loop runs for as many levels as there are in the tree.
  • For each level traversed by the BFS, the inner for loop runs for the number of nodes at that level.
  • Inside the inner loop, each node's value is appended to a list, and then a helper function f(t) is called, which sorts the list and finds the minimum number of swaps needed to sort it.
  • The sorting operation in f(t) is O(k log k) where k is the number of nodes at a particular level.
  • The swap operation inside f(t) has a worst-case time complexity of O(k) for each level, as each element could potentially need to be moved once.

Combining these, the overall time complexity of the function is O(n log k + n), as the sorting is the most significant operation and occurs at each level. However, since k can vary and might be much smaller than n, particularly in balanced trees, the actual time complexity on average cases could be lower. The worst-case time complexity, when all nodes are on a single level (degenerate tree), would be O(n log n).

Space Complexity

  • BFS requires a queue that will at most store all nodes at the widest level of the tree. This gives us O(w) space complexity, where w is the maximum width of the tree.
  • The list t that stores node values of a level will at most store w integers.
  • The dictionary m in the helper function f(t) also stores at most w entries.
  • The deque object itself, in the worst case, would occupy space proportional to the number of nodes at the widest level.

Therefore, the overall space complexity is O(w), where w is the width of the tree, which is the main factor that determines the space usage of the algorithm.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ