Comment by westernmostcoy

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?

That is why you discuss the implementation in-person and ask questions about the design decisions...

As if people who interview for Google don't just look up the most common interview questions and memorize answers before the interview...