Solving the infamous “inverting a binary tree” problem

Summary

The web content describes a method for solving the "invert a binary tree" problem, commonly encountered in technical interviews.

Abstract

The article discusses the approach to solving the "invert a binary tree" problem, which gained attention due to its association with Google's interview process and the problem's perceived complexity. The author breaks down the solution into simple steps, emphasizing the use of recursion to swap the left and right children of each node in the tree. The solution involves a base case for non-existent nodes, a straightforward swap of child nodes, and the application of the same logic to the children recursively. The author provides a Python one-liner for variable swapping and reassures that handling non-existent child nodes is inherently covered by the base case. A helper function is suggested to apply the inversion logic starting from the root node, and the article concludes with an invitation for readers to test their code on LeetCode and follow the author for more content.

Opinions

The author believes that the "invert a binary tree" question is not as intimidating as it sounds and can be tackled with clear, step-by-step logic.
Recursion is deemed almost essential for tree problems, as it naturally aligns with the structure of trees.
The problem is approachable even if the interviewee is not familiar with such questions, as it can be broken down into intuitive steps.
The author suggests that the base case effectively handles the edge case of non-existent child nodes, simplifying the solution.
There is an implication that the Google interview process, which includes such problems, is rigorous and may sometimes be criticized for its appropriateness for the role in question.
The article encourages engagement by inviting readers to submit their solutions to LeetCode and to follow the author for further insights into coding interviews and related topics.

Solving the infamous “inverting a binary tree” problem

This tweet initially drew a lot of attention because:

1/ It’s about the Google interview process.

2/ The problem “invert a binary tree” sounds tricky and obscure.

3/ It’s from a well-known individual within the developer community.

To be clear, this post is about how to solve the problem. While I agree that perhaps asking this question may not have been appropriate for someone in this situation (writing such a popular library), I also don’t think this question isn’t as scary as it might sound. Let’s break it down!

Tree questions almost always use recursion, which makes sense — we need to be able to execute some code on a particular node and its children (which can be accessed via `node.right` and `node.left`).

I’ll break this down into steps, which I’ll then map to a corresponding comment in the code. My mental model is to always think — if given a particular node, what would I want to do with it?

1/ The first case to think about is a base case — what should I do if the node doesn’t exist? Well, if there isn’t anything to “invert”, I’ll just return the node. Pretty straightforward.

2/ If the node *does* exist, what should I do with its children (node.left and node.right)? “Invert” just means the left child should be the right child and vice versa, so it’s as simple as:

node.left, node.right = node.right, node.left

(Python has a nice one-liner for swapping variables.)

3/ Now, I want to apply the exact same logic to the children! So, I’ll call my function on node.left and node.right.

And that’s literally it! A subtlety — what if node.left or node.right doesn’t exist? Recognize that’s *already covered* by your base case — we’ll just return the node which is None!

So we’ll introduce a helper that we can call on each node, then call that helper on the root, and return that value.

Let me know if you have any questions below or want me to write about any other coding questions!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!