Python - BFS with heap(priority queue) nlogn
The idea is to simulate the process of bringing the smallest number you have to the current possition for each level. use heap for the minimum element and dicti
The idea is to simulate the process of bringing the smallest number you have to the current possition for each level. use heap for the minimum element and dictionary to track the index.\n\nExample:\n-    i = 0\n-\t[50, 30, 20, 40] -> swap 50 with 20 and also swap their index and remove 20 from heap\n-\ti = 1\n-\t[20, 30, 50, 40] -> 30 is the minimum so don\'t swap it just pop it from heap and keep going forward\n-   i = 3\n-   [20, 30, 50, 40]  -> swap 50 with the minimum 40 and keep going forward\n-   i = 4\n-   [20, 30, 40, 50] -> now the level is sorted and we have a total of 3 operation.\n```\nclass Solution:\n    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n        minOperation = 0\n        queue = deque([root])\n\n        while queue:\n            newLevel = []\n            # create a new level\n            for elem in queue:\n                if elem.left:\n                    newLevel.append(elem.left)\n                if elem.right:\n                    newLevel.append(elem.right)\n            \n            # process cost each level I have in the queue to be sorted\n            heap = [node.val for node in queue]\n            heapq.heapify(heap)\n            index = {node.val: i for i, node in enumerate(queue)}\n\n            # do the simulation of taking out the minumum and swapping it\n            # if the current element is not the smallest you swap it with the smallest element\n            # and pop from your heap\n            for i, element in enumerate(queue):\n                if element.val != heap[0]:\n                    index[element.val] = index[heap[0]]\n                    index[heap[0]] = i\n                    queue[i], queue[index[element.val]] = queue[index[element.val]], queue[i]\n                    minOperation += 1\n                heapq.heappop(heap)\n            \n            queue = newLevel\n\n        return minOperation\n```
['Breadth-First Search', 'Heap (Priority Queue)']