Clean and concise python solution with good explaination
IntuitionThis problem includes breaking it down into 2 parts:
Level order Traversal of Tree - Textbook BFS
To know how many swaps we need to sort the array.
I b
# Intuition
This problem includes breaking it down into 2 parts:
1. Level order Traversal of Tree - Textbook BFS
2. To know how many swaps we need to sort the array.

I believe the actual problem is teaching us about the 2nd point. There are several ways we can achieve this. But I've used the greedy which is simpler to understand. 

# Approach
1. As mentioned above, textbook BFS for level order traversal, nothing crazy going on.
2. we'll create an temporary array at each level which will basically contain the values of all node on that level and we'll call the sorted_operations function on that array which will tell us that "This many steps needed to sort this level" which we will add to ```ops``` which is essentially the final steps to sort all levels.
3. logic behind the ```sorted_operations``` function :
    - we make a copy of original ```arr``` and we make a copy of that array
    - Next thing we want to do is sort the copy array ```temp``` and a result variable ```res``` which will tell us the swaps we need to make array sorted.
    - now we'll compare the position of the element in the original array and sorted copy of the array
    - The value at  index ```i``` in temp will tell us ideal element at that position, but the value at index ```i```in the original array is the actual element present at that index.
    -  so whenever we find the mismatch between indexes and elements, that means we need one swap to make it right, so we increase ```res``` by one. But we're not done here, we will swap the actual element and "wrong" element in the original array before going into next iteration.
    - How we achieve this, we get the index of the "right" element from the sorted copy and swap that index and current index in the actual array.

And we return ```ops``` at the end of main function.

# Complexity
- Time complexity:
    ```O(N)``` for BFS and ```O(NlogN)``` for getting the no. of swaps.

- Space complexity:
```O(N)``` where N is no. of nodes in the tree and it comes from using a deque

# Code
```python3 []
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        if not root:
            return root
        q = deque([root])
        ops = 0

        while q:
            temp = []
            for _ in range(len(q)):
                node = q.popleft()
                temp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ops += self.sorted_operations(temp)
        return ops

    def sorted_operations(self,arr):
        res = 0
        temp = arr.copy()
        temp.sort()
        for i in range(len(arr)):
            if arr[i] != temp[i]:
                res+=1
                idx = arr.index(temp[i])
                arr[i],arr[idx] = arr[idx],arr[i]
        return res
```

please upvote if it was helpful!
['Tree', 'Breadth-First Search', 'Python3']