A huge tree

What is a binary tree and why would I ever want to reverse it

Posted Wed May 08 2019

You have probably already heard the horror stories of code interviews where they ask you to reverse a binary tree on a whiteboard. (if not check this blog post that I profoundly disagree with)

Well, a few days ago I was in that exact situation. And I had no idea what the interviewer was talking about. So what are these binary trees and why is it so critical that you know how to inverse them? Let’s find out.

What is a binary tree? 

A binary tree is a very simple data structure that as the name suggests looks like an upside-down tree.

A binary tree

This structure is mainly used for searching. For example, if we needed to find 4 in this structure quickly, we would need only to make 2 binary decisions. If we scale this up to 1000 nodes, we would only need about 10 choices. There are other options still, like self-balancing binary trees but let’s keep it simple at the moment, and just focus on balanced binary trees.

Let’s invert them 

Ok so now that we know what it is let’s start with inverting a binary tree. What do we mean by that? It’s actually very straightforward. We turn this:

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

into

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

We flip the entire structure horizontally. So 7 and 2 are flipped, and the 2 children are also flipped. All the way down.

Down to code 

As we are good OOP developers, we are first going to start with our tree. A binary tree is nothing more than a collection of points, called nodes, with 2 children: a left and a right one. So first we are going to create a Node object.


(I’ve added value to the object as well, just to give it a practical use)

Now that we have the Node object it’s time to create a tree.

At this point we have a data structure that looks like this:

A binary tree with labels

This is all set up, time to move on to the swapping. If we break the problem down to its core, we just want to swap the children of a node. Like this:

We take the Node and create (and return) a new Node with the children swapped. We now have:

A binary tree that only inverted one level

At first, glance that looks like we completed the task, but if you look a tiny bit deeper, you might see that we only inverted one level. The lower levels are in the same place (but on the other side of the branch).

To switch those we actually just have to repeat this process till we run out of levels. Now that sounds like a recursive function.

Let’s run through it:

The first thing to note is that our function signature changed. We now also accept null values. Why? Well once we hit bottom, there aren’t any children left. getRight() will return null. This null will indicate that we are at the end of our loop.

next up is that if check:

This is that check for when we run into a null value as described above.

Now the meat of the algorithm:

This is the recursive method. Every time we pass this, we go one level deeper. If we hit bottom, that if will take care of it and it stops. If not, we swap the values and bubble it back up to the level above.

That’s it. Inverting a binary tree is 10 lines of code. It’s actually pretty simple.

Cool, so when would I actually want to inverse a Binary tree? 

I have no idea. I’m sure some brilliant people on Reddit or Twitter will have a trove of useful functionality, but I sure can’t think of one.

In my opinion, this is just one of those job interview questions that solely exist so the interviewer can feel smart. You could argue that this is a simple test to see if the candidate can think recursively, but I believe that an open conversation about the interests of the candidate + maybe a small take-home test would give way more insights.

Hey thanks for reading!

Hope you enjoyed this post. There is no comments section here, if you've ever seen the YouTube comments section you'll probably understand why. If you have any remarks or comments on this topic, you can find links below to social media discussions

Mother board

Connect microservices with the help of GRPC

Posted Sun Jul 23 2017

Microservices can solve a lot of architectural problems, and sometimes create a few fun new ones. A big problem however is connecting these services to each other.Can GRPC lend a hand here?

Continue reading
Bird's eye view of a landscape

A bird's eye view on API development

Posted Sun Nov 15 2015

So you want to build a web API. You have to start somewhere, why not here

Continue reading
A chair and a washbin

The economics of clean code

Posted Thu Feb 06 2020

Clean code makes projects more comfortable to work with and improves shelf life. Its the antagonist of vile legacy codebases that are unmaintainable. Then why do we see it all the time?

Continue reading