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)…
