Invert a binary tree.

1 2 3 4 5 |
4 / \ 2 7 / \ / \ 1 3 6 9 |

to

1 2 3 4 5 |
4 / \ 7 2 / \ / \ 9 6 3 1 |

Trivia:

This problem was inspired by this original tweet by Max Howell:

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.

Analysis

This problem can be solved by using both recursion and bread first traverse or Level order traverse.

We first invert the left tree and right tree, then put the inverted right tree as the left child,

[Read More...]