Comment by tzs

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