BFS | Map | List | Solution for LeetCode#2471
IntuitionThe problem requires finding the minimum number of operations to make each level of a binary tree sorted in ascending order. The intuition is to perfor
![image.png](https://assets.leetcode.com/users/images/6f3477ae-e451-4e7d-aa29-fb84ff0aa83d_1734930551.8932738.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires finding the minimum number of operations to make each level of a binary tree sorted in ascending order. The intuition is to perform a level-order traversal (BFS) and for each level, calculate the minimum number of swaps needed to sort the values.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Perform a level-order traversal using a queue.
2. For each level:
	- Collect the node values in a list.
	- Calculate the minimum number of swaps needed to sort this list.
	- Add this count to the total operations.
3. To calculate the minimum swaps:
	- Create a sorted copy of the level's list.
	- Use a map to track the original indices of values.
	- Compare the original list with the sorted list and swap as needed.
	
# Complexity
- Time complexity: O(nlogn), where n is the number of nodes
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code Option-01
```java []
/**
 * 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) {
        Queue<TreeNode> que=new LinkedList<>();
        boolean[] visit=new boolean[100001];
        List<Integer> list;
        int cnt=0;


        // Initialize BFS
        visit[root.val]=true;
        que.add(root);
        while(!que.isEmpty()){
            
            Queue<TreeNode> tmpQ=new LinkedList<>(); 
            tmpQ.addAll(que); //Maintaining temp Queue for storing next level nodes into "que"
            que.clear(); 

            list=new ArrayList(); //Storing list of nodes for the same level 
            while(!tmpQ.isEmpty()){
                TreeNode node=tmpQ.poll();
                if( node.left!=null && !visit[node.left.val] ){
                    visit[node.left.val]=true;
                    que.add(node.left);
                    list.add(node.left.val);
                }
                if( node.right!=null && !visit[node.right.val] ){
                    visit[node.right.val]=true;
                    que.add(node.right);
                    list.add(node.right.val);
                }
            }
            cnt+=minNoOperations(list); //Finding the minimum operations for strictly increasing order
        }


        return cnt;
    }


    int minNoOperations(List<Integer> list){
        int cnt=0;
        List<Integer> listSort=new ArrayList();
        Map<Integer, Integer> map=new HashMap();

        //Storing Hash(key, value) for list-value and list-index
        for(int i=0; i<list.size(); i++){
            map.put(list.get(i), i);
        }

        listSort.addAll(list);
        Collections.sort(listSort); //Having sorted list into variable "listSort"

        //Comparing "list" with "sortedList" and swapping with help of "map"
        for(int i=0; i<list.size(); i++){
            if(list.get(i)!=listSort.get(i)){
                int idxS=i;
                int idxT=map.get(listSort.get(i));

                Collections.swap(list, idxS, idxT); //Swapping the values between idxS and idxT
                map.put(list.get(idxS), idxS); //Updating "map" value for idxS
                map.put(list.get(idxT), idxT); //Updating "map" value for idxT

                cnt++;
            }
        }

        
        return cnt;
    }

}
```



# Code Option-02: Without using "tmpQ"
![image.png](https://assets.leetcode.com/users/images/6793c725-6ba7-428a-a513-0538ae76884c_1734931331.5879633.png)

```java []
/**
 * 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) {
        Queue<TreeNode> que=new LinkedList<>();
        boolean[] visit=new boolean[100001];
        List<Integer> list;
        int cnt=0;


        // Initialize BFS
        visit[root.val]=true;
        que.add(root);
        while(!que.isEmpty()){
            
            int levelSize=que.size();

            list=new ArrayList(); //Storing list of nodes for the same level 
            for(int i=0; i<levelSize; i++){
                TreeNode node=que.poll();
                if( node.left!=null && !visit[node.left.val] ){
                    visit[node.left.val]=true;
                    que.add(node.left);
                    list.add(node.left.val);
                }
                if( node.right!=null && !visit[node.right.val] ){
                    visit[node.right.val]=true;
                    que.add(node.right);
                    list.add(node.right.val);
                }
            }
            cnt+=minNoOperations(list); //Finding the minimum operations for strictly increasing order
        }


        return cnt;
    }


    int minNoOperations(List<Integer> list){
        int cnt=0;
        List<Integer> listSort=new ArrayList();
        Map<Integer, Integer> map=new HashMap();

        //Storing Hash(key, value) for list-value and list-index
        for(int i=0; i<list.size(); i++){
            map.put(list.get(i), i);
        }

        listSort.addAll(list);
        Collections.sort(listSort); //Having sorted list into variable "listSort"

        //Comparing "list" with "sortedList" and swapping with help of "map"
        for(int i=0; i<list.size(); i++){
            if(list.get(i)!=listSort.get(i)){
                int idxS=i;
                int idxT=map.get(listSort.get(i));

                Collections.swap(list, idxS, idxT); //Swapping the values between idxS and idxT
                map.put(list.get(idxS), idxS); //Updating "map" value for idxS
                map.put(list.get(idxT), idxT); //Updating "map" value for idxT

                cnt++;
            }
        }

        
        return cnt;
    }

}
```
['Java']