A Visual Guide to How to Actually Invert a Binary Tree
Published: 2020-08-16 11:38:36

---
title: A Visual Guide to How to Actually Invert a Binary Tree
published: true
description: This is the famous question that Homebrew author Max Howell famously got wrong in a Google Interview. Hopefully this prevents you from having the same misfortune!
tags: 
cover_image: https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/invert-a-binary-tree-cover-image.png
canonical_url: https://algodaily.com/challenges/invert-a-binary-tree
---

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

<blockquote><p lang="en" dir="ltr">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.</p>&mdash; Max Howell (@mxcl) <a href="https://twitter.com/mxcl/status/608682016205344768?ref_src=twsrc%5Etfw">June 10, 2015</a></blockquote></script>

<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/invert-a-binary-tree-cover-image.png" class="img-fluid" />

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:

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

_This lesson was originally published at [https://algodaily.com](https://algodaily.com/challenges/invert-a-binary-tree), where I maintain a technical interview course and write think-pieces for ambitious developers._

---

{% youtube aFws303_XOc %}

This is the famous question that `Homebrew` author `Max Howell` [famously got wrong in a Google Interview](https://twitter.com/mxcl/status/608682016205344768?lang=en). Hopefully this prevents you from having the same misfortune!

Let's think about brute force-- how would we do it without any clever algorithms? We can start with a very basic input as follows:


```
  1
 / \
2   3
```



So to invert it vertically, we'd start at `1`, where there's nothing to flip or swap, and it would stay put. We've now processed the first row. 

Moving on to the second, we encounter `2` and `3`, so we'd swap them and get:

<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/invert-a-binary-tree-image1.png" class="img-fluid" />



```
  1
 / \
3   2
```





Interesting, this seems to have inverted it! Is it as simple as swapping when there's more than one node?

What if we had more than two nodes to swap per level though? If there was an additional level, it might look like this:





```
      1
     / \
    3   2
   / \   \
  4   5   3
```



That final row is currently directionally `4 -> 5 -> 3`, but we'd want the outcome to be `3 -> 5 -> 4` to be properly inverted.

However, we can achieve this by doing two separate swaps. Notice that the below is what we'd get if we swapped `4` and `5` to obtain `5 -> 4`, and then swapping `5 -> 4` with `3`.

<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/invert-a-binary-tree-image2.png?bust=1" class="img-fluid" />



```
      1
     / \
    2   3
   /   / \
  3   5   4
```



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

<img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/invert-a-binary-tree-image3.png" class="img-fluid" />

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:

```js
function invertTree(head) {
  if (head) {
    var temp = head.left;
    head.left = head.right;
    head.right = temp;

    invertTree(head.left);
    invertTree(head.right);
  }

  return head;
}
```

Check out more visual tutorials for [technical challenges at AlgoDaily.com](https://algodaily.com/curriculum) and try out [our daily coding problem newsletter](https://algodaily.com/challenges/daily)!