C++ Solution || Easy to Understand
Minimum Operations to Sort Tree LevelsThis project contains a solution to the problem of finding the minimum number of operations required to sort the values at
# Minimum Operations to Sort Tree Levels

This project contains a solution to the problem of finding the minimum number of operations required to sort the values at each level of a binary tree.

## Problem Description
Given a binary tree, the task is to find the minimum number of operations required to sort the values at each level of the tree in ascending order. An operation is defined as swapping two elements in an array.

### Example
#### Input:
A binary tree:
```
        1
      /   \
     3     2
    / \   / \
   7   6 5   4
```
#### Output:
```
3
```
#### Explanation:
- Level 1: [1] (Already sorted)
- Level 2: [3, 2] -> Requires 1 swap to become [2, 3]
- Level 3: [7, 6, 5, 4] -> Requires 2 swaps to become [4, 5, 6, 7]
Total swaps = 1 + 2 = 3.

## Approach
The solution involves the following steps:
1. Traverse the tree level by level using a breadth-first search (BFS).
2. For each level, collect the node values in an array.
3. Count the minimum number of swaps required to sort the array using the `minSwaps` function.
4. Sum up the swaps for all levels to get the result.

### Key Functions
- **`minSwaps(vector<int>& arr)`**:
  This function calculates the minimum number of swaps required to sort an array.

- **`minimumOperations(TreeNode* root)`**:
  This function performs the BFS traversal and computes the total number of swaps for all levels.

## Complexity Analysis
### Time Complexity:
- BFS traversal of the tree: $$O(n)$$, where $$n$$ is the number of nodes in the tree.
- Sorting and calculating swaps for each level: $$O(k \log k)$$ per level, where $$k$$ is the number of nodes at the level.
  
Overall complexity: $$O(n \log k)$$, where $$k$$ is the maximum number of nodes at any level.

### Space Complexity:
- Queue for BFS: $$O(w)$$, where $$w$$ is the maximum width of the tree.
- Additional space for storing node values at each level: $$O(k)$$.
  
Overall complexity: $$O(w + k)$$.

## Code
```cpp
/**
 * 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 minSwaps(vector<int>& arr) {
        int n = arr.size(), count = 0;
        vector<pair<int, int>> vec;
        for (int i = 0; i < n; i++) {
            vec.push_back({arr[i], i});
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < n; i++) {
            if (vec[i].first != arr[i]) {
                swap(vec[vec[i].second], vec[i]);
                i--;
                count++;
            }
        }
        return count;
    }

    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            int size = q.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* curr = q.front();
                q.pop();
                vec.push_back(curr->val);
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
            ans += minSwaps(vec);
        }
        return ans;
    }
};
```


![1721315779911.jpeg](https://assets.leetcode.com/users/images/6e0f2ded-30fd-4835-9e98-0a00da1a3e95_1734947766.187424.jpeg)



['Tree', 'Breadth-First Search', 'Binary Tree', 'C++']