[Java] Invert binary tree

Given a balanced and complete binary tree invert it, all right children become left children and all left children become right children.

Example:

    a
   / \
  b   c
 / \  /
d   e f

becomes:

  a
 / \
 c  b
 \  / \
  f e  d

We need to visit each node and invert its children. We can accomplish this in two ways, BFS or DFS.

If we use BFS, we add nodes to a queue and process them in the order we first saw them, which means when we reach the last level we will have O(N/2) nodes in the queue, which is O(N) space.

If we use DFS we add nodes to a stack, or we approach the problem recursively (or we use a queue and remove from the end of it), then we will have O(log N) nodes in the stack since we keep going down to each leaf before returning, therefore we won't add more nodes than the path to the leaf, which in a balanced and complete tree is O(log N) at most, the height of the tree.

Note that the balanced and complete tree is the worst case as we have the most nodes to handle and each level is full.

You can check my implementation of invertBST on my Gist along with some tests in InvertBSTJTests.