### Invert a Binary Tree (Main Thread)

Here is the interview question prompt, presented for reference.

Can you invert a `binary tree` over its vertical axis? This is a famous problem made popular by this tweet:

Google: 90% of our engineers use the software you wrote (Homebrew), but you canâ€™t invert a binary tree on a whiteboard so fuck off.— Max Howell (@mxcl) June 10, 2015

Given a `binary tree` like this:

``````     4
/   \
2     7
/ \   / \
1   3 6   9
``````

Performing an inversion would result in:

``````Output:

4
/   \
7     2
/ \   / \
9   6 3   1
``````

The definition of a tree node is as follows:

``````function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
``````

### Constraints

• Number of nodes in the tree <= `1000`
• The nodes will always contain integer values between `-1000000000` and `1000000000`
• Expected time complexity : `O(n)`
• Expected space complexity : `O(logn)`

You can see the full challenge with visuals at this link.

Challenges â€¢ Asked over 3 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Invert a Binary Tree.

Andre Commented on Mar 24, 2021:

Hey there,

Great exercise, thank you!
I wanted to point out the test case #3 is incorrect.
It defines inverted_tree2.right.left = Node(8) where it should actually be = Node(3).
As a consequence, my submission is failing that test and is not getting accepted.

Thank you!

Jake from AlgoDaily Commented on Mar 24, 2021:

Hi Andre,

Thanks for the heads up-- this is fixed!