# Invert [[binary-tree|Binary Tree]]
https://leetcode.com/problems/invert-binary-tree/
## Solution 1: Recursion
- Complexity: $O(n)$ as each node is iterated once. $O(\lg n)$ call stack depth.
```python
if not root:
return None
root.left = self.invertTree(root.right)
root.right = self.invertTree(root.left)
return root
```
## Solution 2: Iteration
Implemented with [[deque]].
```python
if not root:
return None
queue = collections.deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return root
```
Implements [[level-order]].