> [Ex-Googler here] Truth be told this is a trivial question to be asked during an algo interview and as an interviewer I'd consider this a warm-up. Otherwise it's a rather poor question since either you know how to do it (ie, you have an idea about recursion) or you don't - there aren't too many shades of grey or possible follow-up questions that I can ask to probe the depth of your knowledge.
It is a terrible question.
First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree.
If the questioner meant mirror a binary tree (swap left & right at each node), then it is a no-op. You do not need to modify memory to do it. Left & right are just labels for two pointers. You can just swap the order your variables in whatever struct defines your node and cast it against your existing memory (or change what your accessors return in a derived class or create a reverse iterator or however you want to implement it) and there you go, a "reversed" tree with zero overhead.
Either way, it is a terrible question unless you wanted to see if someone understood the difference between how a data structure is drawn on a whiteboard for humans vs. how it actually works. Maybe they were actually asking that question, but that seems highly unlikely.
And if they actually meant for you to recurse down and swap left and right on everything, it would dramatically lower my opinion of them because it would make me wonder if they knew the difference between how a binary tree is drawn on a whiteboard vs. how it is laid out in memory.
> First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree.
Inversion is a transformation that maps directed graphs to directed graphs. Binary trees are a subset of directed graphs, so applying inversion to them is not unreasonable. That subset is not closed under inversion, so you can get results that are not binary trees, but I see nothing in the question that implies that the interviewer was asking for the output to be a binary tree.
That may even be one of the points the interviewer wants to see the candidate address. Since the output no longer has a single node from which all other nodes can be reached, in addition to just inverting it they may want the candidate to mention the need to have some new auxiliary data structure to keep track of the multiple root nodes (and perhaps note that in the inverted tree each node only has one outgoing link, so if we are inverting in place each has room for two, so we can use that now available second link space to make a linked list of the roots, so we don't need any extra storage for the new root list data structure).
> if they actually meant for you to recurse down and swap
While only the person asking this question knows for sure I'd assume that was the intention.
It's not a _terrible_ question - it's just a recursive equivalent of FizzBuzz. You would treat this as a way of making a (good) candidate gain some confidence. And that alone is extremely important since the more at ease the candidate is the better the signal that you're getting. What I was trying to say there was that if I asked that as a warm-up and didn't get a satisfactory response very very soon I'd realise that your man has no clue about recursion and would move to the main question, choosing one that does not involve it. It would be something easier than I'd ask otherwise and would be closer to real-life scenarios - like first solving a simple problem, then parallelising the solution and correctly managing concurrent access.
> First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree
Just because someone wrote on Twitter with limited number of characters that the problem was to "invert a binary tree", does not mean there were no clarification from the recruiter.
> And if they actually meant for you to recurse down and swap left and right on everything, it would dramatically lower my opinion of them because it would make me wonder if they knew the difference between how a binary tree is drawn on a whiteboard vs. how it is laid out in memory.
If you're thinking about making a real structure, I believe you should recurse down and swap. If you don't do this, rotating, joining etc, could be a real pain.
If they said "swap left & right at each node" it would have been easy. But they used a term that doesn't even yield an example in google searches - what kind of "inversion" do they have in mind? It's as if everyone is on the same page but me.
"Invert a binary tree" and "inverting a binary tree" both give me as the first result in Google this Quora question where someone gives an example and asks how to do it: http://qr.ae/7NDCg4
At my university it's common to call acyclic, connected graph a tree. We distinguish between rooted and unrooted trees. For example, minimal spanning tree doesn't really have to be rooted, it just has no cycles.
It is a terrible question.
First, you can't invert a binary tree (as in flip upside down). If you did, you'd end up with multiple roots and since all binary trees are rooted, you'd no longer have a binary tree. It'd be a tree, just not a binary tree.
If the questioner meant mirror a binary tree (swap left & right at each node), then it is a no-op. You do not need to modify memory to do it. Left & right are just labels for two pointers. You can just swap the order your variables in whatever struct defines your node and cast it against your existing memory (or change what your accessors return in a derived class or create a reverse iterator or however you want to implement it) and there you go, a "reversed" tree with zero overhead.
Either way, it is a terrible question unless you wanted to see if someone understood the difference between how a data structure is drawn on a whiteboard for humans vs. how it actually works. Maybe they were actually asking that question, but that seems highly unlikely.
And if they actually meant for you to recurse down and swap left and right on everything, it would dramatically lower my opinion of them because it would make me wonder if they knew the difference between how a binary tree is drawn on a whiteboard vs. how it is laid out in memory.