DEV Community

Cover image for A Visual Guide to How to Actually Invert a Binary Tree
Jake Z.
Jake Z.

Posted on • Updated on • Originally published at algodaily.com

A Visual Guide to How to Actually Invert a Binary Tree

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;
}

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.


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!

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:


  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.


      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.

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:

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 and try out our daily coding problem newsletter!

Top comments (10)

Collapse
 
pentacular profile image
pentacular

The first insight here is that the structure of a binary tree is determined by the predicate used to determine which path to follow.

So, you can invert the tree by inverting the predicate -- e.g., instead of testing for a < b, test for a > b.

We don't need to change the structure of the tree at all to invert it -- we can just change how we will traverse it. :)

The second insight should be that the predicate's decisions are encoded into the choice of 'left' or 'right'.

Which means that you can invert the tree by swapping the branch labels 'left' and 'right'.

It doesn't matter what order you swap the branch labels in -- the result will be the same.

The third insight should be that you don't need to swap the branch labels -- you can just look at them backward them as you traverse the tree to look things up.

Collapse
 
vlasales profile image
Vlastimil Pospichal

Sometimes you need invert the tree for 3rd party library.

Collapse
 
jacobjzhang profile image
Jake Z.

Great takeaways! I totally agree with the first two points. Do you mind expanding on "you don't need to swap the branch labels", particularly which labels we're talking about?

Collapse
 
pentacular profile image
pentacular • Edited

You have two branches -- say 'left' and 'right'.

Instead of modifying the tree you can modify how you traverse it.

Where you would choose 'left', instead choose 'right'.
Where you would choose 'right', instead choose 'left'.

Thread Thread
 
jacobjzhang profile image
Jake Z.

Ah gotcha, yes!

Collapse
 
vlasales profile image
Vlastimil Pospichal
function invertTree(head) {
    if (head) {
        var temp = invertTree(head.left);
        head.left = invertTree(head.right);
        head.right = temp;         
    }
    return head;
}
Collapse
 
codinglanguages profile image
Your DevOps Guy

Great visual explanation, Jake.

Just to add something to this, this problem can be solved iteratively in two different ways:

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

Collapse
 
jacobjzhang profile image
Jake Z.

Wonderful points, thank you! I'll add these to the tutorial.

Collapse
 
belinde profile image
Franco Traversaro

I hoped for a better solution... Recursive functions are limited by the call stack maximum size, so in case of huge trees (or incredibly slim and deep ones) we should linearize the solution. Unfortunately I don't see an easy approach, given the data structure we have; probably we should add an ordered list of visited nodes and try every path from root to the leafs, but I'm on the phone now and it's difficult to write a solution. I'll try today.

Collapse
 
katiekodes profile image
Katie • Edited

What did you use to draw the illustrations? So nice!