In this case, it means to reverse the binary tree, so that you get the largest item by iterating down the left branch to the bottom of the tree. You would do this by breadth-first scanning the tree, swapping the left and right pointers as you go.
Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf.
If this was really about "reversing" the tree, as you mention, the question seems more likely to address how the candidate approaches the situation. Like, he should start by making sure they both agree on what the question actually means.
Once that's out of the way, it seems relatively easy to come up with a naive solution, without having memorised any algorithms. It seems more like a case of brainfreeze to me, which can be sort-of fixed with practice (which in turn many candidates refuse to do: the dreaded "If I have to cram for the interview, I don't want the job" statement.)
So maybe he really wasn't a good fit for Google, despite apparently being a rockstar developer. Hey, startups need rockstar devs too.
I was gonna say, who calls reversing a tree's ordering inverting?
> Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf.
Whaaaaa? I can't find this, but it seems like such a weird operation. Got a link?
