[sgeisenh]

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!

[peteretep]

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