Simple and Easy Solution  with BFS || C++| Java | Python | JavaScript
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]IntuitionThe problem requires arranging the values at each level of a binary tree in strictly inc
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

```cpp []
class Solution {
public:
    int minimumOperations(TreeNode* root) {
        if (!root)
            return 0;

        queue<TreeNode*> q;
        q.push(root);
        int operations = 0;

        while (!q.empty()) {
            int size = q.size();
            vector<int> level;

            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }

            vector<int> sort_level = level;
            sort(sort_level.begin(), sort_level.end());
            unordered_map<int, int> mp;

            for (int i = 0; i < level.size(); ++i) {
                mp[level[i]] = i;
            }

            for (int i = 0; i < level.size(); ++i) {
                while (level[i] != sort_level[i]) {
                    ++operations;
                    int cur = mp[sort_level[i]];
                    mp[level[i]] = cur;
                    swap(level[i], level[cur]);
                }
            }
        }

        return operations;
    }
};
```

```python []
class Solution:
    def minimumOperations(self, root):
        if not root:
            return 0
        
        from collections import deque
        q = deque([root])
        operations = 0

        while q:
            size = len(q)
            level = []

            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            sort_level = sorted(level)
            mp = {v: i for i, v in enumerate(level)}

            for i in range(len(level)):
                while level[i] != sort_level[i]:
                    operations += 1
                    cur = mp[sort_level[i]]
                    mp[level[i]] = cur
                    level[i], level[cur] = level[cur], level[i]

        return operations
```

```java []
class Solution {
    public int minimumOperations(TreeNode root) {
        if (root == null)
            return 0;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int operations = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null)
                    q.add(node.left);
                if (node.right != null)
                    q.add(node.right);
            }

            List<Integer> sort_level = new ArrayList<>(level);
            Collections.sort(sort_level);
            Map<Integer, Integer> mp = new HashMap<>();

            for (int i = 0; i < level.size(); i++) {
                mp.put(level.get(i), i);
            }

            for (int i = 0; i < level.size(); i++) {
                while (!level.get(i).equals(sort_level.get(i))) {
                    operations++;
                    int cur = mp.get(sort_level.get(i));
                    mp.put(level.get(i), cur);
                    Collections.swap(level, i, cur);
                }
            }
        }

        return operations;
    }
}
```

```javascript []
class Solution {
    minimumOperations(root) {
        if (!root) return 0;

        const q = [root];
        let operations = 0;

        while (q.length > 0) {
            const size = q.length;
            const level = [];

            for (let i = 0; i < size; i++) {
                const node = q.shift();
                level.push(node.val);
                if (node.left) q.push(node.left);
                if (node.right) q.push(node.right);
            }

            const sort_level = [...level].sort((a, b) => a - b);
            const mp = new Map();
            for (let i = 0; i < level.length; i++) {
                mp.set(level[i], i);
            }

            for (let i = 0; i < level.length; i++) {
                while (level[i] !== sort_level[i]) {
                    operations++;
                    const cur = mp.get(sort_level[i]);
                    mp.set(level[i], cur);
                    [level[i], level[cur]] = [level[cur], level[i]];
                }
            }
        }

        return operations;
    }
}
```

# Intuition
The problem requires arranging the values at each level of a binary tree in strictly increasing order with the minimum number of swaps. This can be seen as solving a series of sorting problems for each level of the tree. Since swapping values is allowed, the minimum number of swaps corresponds to sorting each level using a cycle-based approach.

# Approach
1. **Level-Order Traversal**: Perform a level-order traversal of the tree using a queue. At each level, collect the node values in a list.
2. **Sort and Count Swaps**: For the collected values at each level:
   - Create a sorted copy of the level values.
   - Use a mapping of current indices to target indices in the sorted list.
   - Count the number of swaps needed to sort the level using cycle detection.
3. **Repeat for All Levels**: Repeat this process for every level of the tree and sum up the total swaps.

# Complexity
- **Time Complexity**:
  - Traversing the tree takes $$O(n)$$, where $$n$$ is the number of nodes in the tree.
  - Sorting each level and counting swaps take $$O(k \log k)$$ for a level with $$k$$ nodes. In the worst case, summing over all levels still results in $$O(n \log n)$$ for the entire tree.
  - Overall: $$O(n \log n)$$.

- **Space Complexity**:
  - Storing the queue for level-order traversal takes $$O(w)$$, where $$w$$ is the maximum width of the tree.
  - Storing the level values and their sorted copy takes $$O(k)$$ for each level, but the space is reused across levels.
  - Overall: $$O(w)$$.

### *If you have any questions or need further clarification, feel free to drop a comment! 😊*
['Tree', 'Breadth-First Search', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']