BFS + Cyclic Sort with Explanation
Intuition\nHere we have to count minimum swaps to sort the nodes in each level. \n\n1. So, for getting the nodes in each level, I have used Level order traveral
# Intuition\nHere we have to count minimum swaps to sort the nodes in each level. \n\n1. So, for getting the nodes in each level, I have used `Level order traveral` and then \n2. we will count the `min swaps` for that level\n\n# Approach\nThe level order traversal is the regular level order traversal.\n\nThe tricky part is the sorting. For this approach, we will use `cyclic sort` i.e. if an element is not at its correct place, we will swap the element current index with the correct value.\n\n>Below explanation is for `int minSwaps (List<Integer> list) {}` function\n\nHow we do it is, we have our list of elements in `list`. This has all the elements but may not be in order.\n\nWe will make a copy of this `list` and sort it (`sorted`). `sorted` gives us the final arrangement but to reach to it we have to count the min number of swaps which is our ans. \n\nWe will iterate through every index and for an index `if list(i) != sorted(i)` then we need to swap the value index `i` with the correct element. So, we have the correct element i.e. `sorted(i)` but we need its index in `list` to swap the elements, we use `list.indexOf(correct value)` i.e. `list.indexOf(sorted.get(i))`\n\n\n# Code\n```\nclass Solution {\n    public int minimumOperations(TreeNode root) {\n        int res = 0;\n        Queue<TreeNode> q = new ArrayDeque<TreeNode>();\n        q.add(root);\n        while (!q.isEmpty()) {\n            int n = q.size();\n            List<Integer> list = new ArrayList<Integer>();\n            while (n-- > 0) {\n                TreeNode curr = q.remove();\n                if (curr.left != null) q.add(curr.left);\n                if (curr.right != null) q.add(curr.right);\n                list.add(curr.val);\n            }\n            res += minSwaps(list);\n        }\n        return res;\n    }\n    int minSwaps(List<Integer> list) {\n        int swaps = 0, n = list.size();\n        List<Integer> sorted = new ArrayList<Integer>();\n        sorted.addAll(list);\n        Collections.sort(sorted);\n        for (int i = 0; i < n; i++) {\n            if (list.get(i) != sorted.get(i)) {\n                ++swaps;\n                Collections.swap(list, i, list.indexOf(sorted.get(i)));\n            }\n        }\n        return swaps;\n    }\n}\n```\nThe above code will give us TLE because of this line:\n```Collections.swap(list, i, list.indexOf(sorted.get(i)));``` \nThe reason being, `indexOf` will search using `linear-search` so the searching may take upto `O(n)` time and with the for loop the time complexity may reach ***O(n<sup>2</sup>)*** which results in TLE.\n\nWe can optimize the searching part by introducing a `hashmap`. The hashmap is just a copy of `list` paired with the corresponding index but using the hashmap wil reduce the searching time complexity from `O(n)` to `O(1)`. So, our overall time complexity gets reduced from ***O(n<sup>2</sup>)*** to `O(n)`\n```\nint minSwaps(List<Integer> list) {\n    int swaps = 0;\n    List<Integer> sorted = new ArrayList<Integer>();\n    sorted.addAll(list);\n    Collections.sort(sorted);\n    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();\n    for (int i = 0; i < list.size(); i++)\n        map.put(list.get(i), i);\n    for (int i = 0; i < list.size(); i++) {\n        if (list.get(i) != sorted.get(i)) {\n            ++swaps;\n            int swap_index = map.get(sorted.get(i));\n            map.put(list.get(i), swap_index);\n            map.put(sorted.get(i), i);\n            Collections.swap(list, i, swap_index);\n                \n        }\n    }\n    return swaps;\n}\n```\n***If this solution helped you, please upvote it :)***
['Java']