So, to put it all together: we can perform an in-order traversal and do a swap at each iteration.

A caveat that was pointed out by readers — if we’re dealing with a substantially large binary tree, then a recursive solution might cause problems due to call stack size. There are two ways to get around this:

1. Using a stack to mimic the recursion
2. Using a queue, visiting the levels one by one in a BFS fashion and swapping the left and right nodes to invert the tree.

Here’s what the final code looks like:

1function invertTree(head) {
2  if (head) {
3    var temp = head.left;
4    head.left = head.right;
5    head.right = temp;
6
7    invertTree(head.left);
8    invertTree(head.right);
9  }
10
11  return head;
12}

Complexity of Final Solution

Let n be the number of nodes in the binary tree. We traverse through all n nodes using recursion for O(n) time complexity, and we can have up to logn recursive calls on the stack at once where logn is the depth of the tree for O(logn) space complexity.