Minimum Number of Operations to Sort a Binary Tree by Level

Leetcode Problem:

• Minimum Number of Operations to Sort a Binary Tree by Level

Summary

• This is a solution for the problem of finding the minimum number of operations needed to make the values at each level of a binary tree strictly increasing.

Approach

• This solution uses a level-order traversal to store the node values at each level in a vector
• Then it sorts the node values at each level and checks for any swaps needed to make the values strictly increasing
• The solution keeps track of the number of swaps needed and returns the total number of swaps as the minimum number of operations.

Complexity

• O(n log n) where n is the number of nodes in the tree, due to the sorting operation at each level.

Explanation

• The solution first performs a level-order traversal of the tree and stores the node values at each level in a vector
• Then it sorts the node values at each level and checks for any swaps needed to make the values strictly increasing
• The solution keeps track of the number of swaps needed and returns the total number of swaps as the minimum number of operations.

Solution Code:

/**
 * 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:
    vector equalLevelNode[100001];
    void traversal(TreeNode* root, int level){
        if(root == nullptr) return;
        equalLevelNode[level].push_back(root->val);
        traversal(root->left, level + 1);
        traversal(root->right, level + 1);
    }
    int minimumOperations(TreeNode* root) {
        traversal(root, 0);
        int ans = 0;
        for(int i = 0 ; i <= 100000; i++){
            if(equalLevelNode[i].size() == 0) break;
            unordered_map m;
            vector sorted;
            for(int j = 0 ; j < equalLevelNode[i].size(); j++){
                sorted.push_back(j);
            }
            sort(sorted.begin(), sorted.end(), [&](int a, int b){
                return equalLevelNode[i][a] < equalLevelNode[i][b];
            });
            for(int j = 0; j < sorted.size(); j++){
                m[sorted[j]] = j;
            }
            for(int j = 0; j < sorted.size(); j++){
                if(equalLevelNode[i][sorted[j]] != equalLevelNode[i][j]){
                    ans++;
                    int t = equalLevelNode[i][sorted[j]];
                    equalLevelNode[i][sorted[j]] = equalLevelNode[i][j];
                    equalLevelNode[i][j] = t;

                    sorted[m[j]] = sorted[j];
                    m[sorted[j]] = m[j];
                }
            }
        }
        return ans;
    }
};