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:

1. Swap subtrees 3 and 7
2. Swap subtrees of node 7: 6 and 9
3. 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:

1. Create queue
2. Add root to the queue
3. While queue is not empty
4. Remove first node from the queue
5. If node is not null (not a lead node)
6. Swap its left and right nodes
7. 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;
    }
}