Honestly, is reversing a binary tree something you need to memorize? I assume that's what he/she means by "invert".

Rambling weirdness stream of consciousness, but, yeah you might well be right... how hard can it be to reverse a binary tree? Isn't the "real" solution to sound out the solution as you go, and let the interviewer know what you're thinking?

I've never attempted to do this before, and my compsci is real weak, to the point where I'm going to make an educated guess about what a binary tree even _IS_ so... Let's start with what is a binary tree? Presumably we have a tree where every node has zero or two child nodes. Clue is in the name. In fact, that's an implementation detail, so let's say we have a tree where every node has a place two hold a left and a right node, where either can be null. Guessing that in order to be useful, the nodes need to hold a value. We need to choose a language here, and I know a miniscule amount of Go, and surely the cool kids at Google like Go, so:

    type Node struct {
        Value int
        Left *Node
        Right *Node
    }

And so now we can do something like:

    n := Node{ Value: 50, Left: &Node{ Value: 30, Left: &Node{ Value: 10 } }}
    n.Right = &Node{ Value: 80 }

Now what does it mean to "reverse" a binary tree? Are we simply swapping all Left values for Right values? It feels a bit like there might be a trick here. So let's draw a binary tree with some numbers, and think about what reversing it might look like:

           Input                    Output

            50                        50
        40      60                60      40
      35  45  55  65            65  55  45  35

Actually, that looks pretty reasonable to me, and that's a straight flip of each Node's pieces. I had wondered if I might need to only swap at every other depth, but this just looks like simply swapping over the left and the right branch will work fine.

We can either iterate or recurse here, right, because it's a nested data structure, and I once read almost the first two chapters of SICP, and I'm pretty sure those are the options. So, let's have a quick think about the memory / performance implications of that. I cannot think of a way we can avoid visiting each node here; perhaps there is one, but cards on the table, I can't think of one. So let's assume we have a runtime cost that will grow linearly with the number of nodes. If that's the case, I'm pretty sure that's what the cool kids call O(n) - maybe that's O(1), but I'm sure Wikipedia can tell me.

So the mechanics of switching any given Node looks pretty easy:

    nr := n.Left
    n.Left = n.Right
    n.Right = nr

That should handle nil no problem too. But we also have to switch the children. If my original assumption about having to talk to every node is correct, what the question really wants to do is know if we can do this in a way that isn't too much of a memory hog. Now a simple recursive method would do this, for sure:

    func (n *Node) recursiveReverse() {
        nr := n.Left
        n.Left = n.Right
        n.Right = nr
        if n.Left != nil {
            n.Left.recursiveReverse()
        }
        if n.Right != nil {
            n.Right.recursiveReverse()
        }
    }

But while I know _NOTHING_ about how Go's callstack works, I bet it doesn't do magical optimization to stop it simply growing and growing and growing, which I think the cool kids call "tail optimization". At this point, one turns to the interviewer and says "How big do these trees get?", and makes some point about simple and elegant solutions to problems that make developers lives easy, because hardware and processing power is cheap. Let's assume the interviewer doesn't let you off the hook so easily...

Let's take a second to think about the memory consumption of what we've got here. At the moment, we add a new ... thingy (are they called frames? I have no clue) to our callstack for each child, and our worst case scenario then is the maximum depth of the tree. No-one has told us if our tree balances, but I suspect that if it does, you could then describe the max-depth using a formula involving `log` and the total known nodes. Wikipedia would know.

What else could we do? You could keep an explicit stack of nodes you knew you still needed to be visited, and go depth first. My gut feeling there is that you could write this where you get a worst-case scenario of your stack getting as big as the deepest node, plus one or two. If you wanted a truly iterative approach, you would need to store a pointer to the parent in each Node; there's a memory (or storage) cost to that too, so how often do we actually need to reverse the binary tree? That's a question to think about.

Given all this, then, one comes down to: what's the relative memory pressure that each frame in the call stack exerts, as opposed to pushing a pointer on to the end of an array in Go? Oooh, Go arrays are immutable, so actually you need to think about slices, unless you already know the size of the tree, and can preallocate exactly as much memory as you need. I wonder if there are memory implications there? With my commercial hat on, again, how much does this actually need optimizing?

Anyway, those are the considerations that come to mind; it would be worth checking Wikipedia for a nice iterative approach here, or if there's a sensible known algorithm. I'm going to stick with the recursive version I had above as my whiteboard version.

Did I get the job?

It can't be just mirroring, because there's the obvious zero-op solution because "left" and "right" don't actually mean anything except when you're visualizing it for humans:

  struct NormalNode {
    int value;
    struct NormalNode *left;
    struct NormalNode *right;
  };

  struct ReversedNode {
    int value;
    struct ReversedNode *right;
    struct ReversedNode *left;
  };

  struct ReversedNode *reverseTree(struct NormalNode *root) {
    return (struct ReversedNode *)root;
  }

There. Now left is right and right is left.

This is genius. My C is rusty, but isn't this more than visualising for humans, if I cast a NormalNode as ReversedNode, traversal should be reversed, right? (I.e.reversed->right is normal->left

Yes, everything would be reversed. That version isn't actually how you'd do it if you actually for some reason wanted to use it in real software, it just was for illustration purposes to show "left" and "right" are just names and you don't need to change anything in memory to flip them.

A similar effect could be done in an OO language by having a base class NormalNode with two accessors, getLeft() and getRight() work normally and then a derived ReverseNode where getLeft() called super.getRight() and getRight() called super.getLeft(). With a proper compiler, the whole thing would simply be optimized away.

If you instead use a language with algebraic datatypes, you can get a nice concise implementation. Let's try OCaml:

  type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Leaf
  
  let rec reverse = function
    | Node (L, x, R) -> Node (reverse R, x, reverse L)
    | Leaf           -> Leaf
  

Isn't that nice? And it is even easy to reason about! Unfortunately, OCaml tends to chew up stack space so we're likely to seg fault, but that's okay!

I was going to go with Haskell, which would have looked very similar, but thought I would struggle to reason at all about performance.

>If you rate engineers on their ability to memorize something they could have looked up on Google in 5 seconds, what are you really actually testing?

Repeating what I said earlier - You can't build a plane by opening a physics textbook. Starting with a LARGE pool of fundamental and higher order building blocks allows you to fit them together using whatever skill/talent you have at solving problems, in a MUCH shorter time than someone who doesn't.

Someone who constantly google's basic stuff is a net drag on a team's productivity. Rather than operating at their skill level, they're constantly being distracted by having to task-switch and waste hours researching stuff. The internet isn't going to magically know the exact problem you're working on and whether certain data structures or algorithms are appropriate for solving it, or if they need further tuning depending on what your priorities are, or what have you. Getting questions answered, and googling/learning about CS stuff is great on its own, and should be encouraged as much as possible, but it is not a substitute for actually retaining that knowledge.