I would have failed you as well. The point is to test whether you have a clear picture of what goes on one layer of abstraction below or if you are confined to the surface.

I don't get the fuss about interviews. They seem to largely consist of basic programming exercises.

You don't need to know the solution before hand and it is easily intuited on-the-fly. I would never hold it against someone to miss some corner-cases or maybe go for a naive implementation first.

I remember a few years ago, someone was complaining that they had been rejected for not being able to reverse a binary tree even though they had a copious amount of OSS.

The thought process is simple and it's an exercise that students do within the first few weeks of their freshman year.

    (struct node (value left right))

    (define (reverse-tree root)
      (cond
        [(equal? root 'EMPTY) root]
        [else
             (node (node-value root)
               (reverse-tree (node-right root))
               (reverse-tree (node-left root)))]))
    

A tree is intuitively defined as a recursive data-structure.

There is one base case: when we reach a leaf.

We want to reverse the left and right subtree at every stage of recursion.

Combine all of this and it's done. I would even be content with a pseudo-code implementation.