# 226. Invert Binary Tree - June day 1

Inspiration of this problem comes from Max Howel's interview experience with Google described in this tweet.

# Lets jump to the problem

The idea is to invert every subtree, let's start with a simple example.

As you can see in the below example, just swap children nodes and we will have the resulting tree.

It gets a little trickier with bigger trees, however the principle is basic.

- Start with root node
- Swap its children
- Perform the same process on all nodes

Let's this in an example:

Now let's swap its children:

- Swap subtrees 3 and 7
- Swap subtrees of node 7: 6 and 9
- Swap subtrees of node 3: 2 and 4

Resulting tree will look like this:

This can be solved using either depth first search or breadth first search, we will solve it with BFS to avoid recursion overhead:

- Create queue
- Add root to the queue
- While queue is not empty
- Remove first node from the queue
- If node is not null (not a lead node)
- Swap its left and right nodes
- Add left and right to queue

```
class Solution {
public TreeNode invertTree(TreeNode root) {
var queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
var node = queue.removeFirst();
if(node != null) {
var temp = node.left;
node.left = node.right;
node.right = temp;
queue.add(node.left);
queue.add(node.right);
}
}
return root;
}
}
```