Alright, I guess I'll admit this just sniped me.

Having read the rules it's difficult to know what's considered "fair" for this test - all GC tuning is off the table, sure. But what's bugging me is "Leaf nodes must be the same as interior nodes - the same memory allocation." So what constitutes "the same memory allocation" - literally the exact same call to some opaque internal allocator? If so, shouldn't Java also have to disable JIT to be fair?

Let me offer an alternate interpretation: I will do the same memory allocation if I need to allocate a node, but if my language lets me not allocate a node yet still use that node why should I? Or an alternate argument if you don't like that one: Why must my "node" be `Tree`, rather than `*Tree`?

A central idiom of Go is that zero-values of a type can be useful; a two-line change, no new special-cases, no pooling or such gauche hacks:

    // Count the nodes in the given complete binary tree.
    func (t *Tree) Count() int {
     if t == nil {
      return 1
     }
     return 1 + t.Right.Count() + t.Left.Count()
    }

    // Create a complete binary tree of `depth` and return it as a pointer.
    func NewTree(depth int) *Tree {
     if depth > 0 {
      return &Tree{Left: NewTree(depth - 1), Right: NewTree(depth - 1)}
     } else {
      return nil
     }
    }

I'm sure someone will tell me I "optimized away the work" - but in the end I believe I'm making exactly the same number of method calls on the same type of receiver. If that's not the work, what is?