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 s...
For further actions, you may consider blocking this person and/or reporting abuse
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.
Sometimes you need invert the tree for 3rd party library.
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?
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'.
Ah gotcha, yes!
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.
Wonderful points, thank you! I'll add these to the tutorial.
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.
Since this post exists for almost four years and has a lot of likes and no diagreeing comments I can only imagine that I do not get something that seems obvious to everyone else. Here is what I would have thought would be the correct solution:
should look like
since the recursive solution only ever considers one triangle in a swap. The first triangle is
which becomes
but 2 and 3 still have reference the child nodes they referenced before and now we jump into two seperate executions. So two triangles are considered seperately. One triangle is
which becomes
and the other triangle is
which becomes
How would 5 suddenly become a child of 3? The algorithm itself seems to be correct but I do not understand how this algorithm produces the example given in the article.
What did you use to draw the illustrations? So nice!