> I need a tree. Sorted lg(n) structures are incredibly useful, and maps aren't sorted, but as it stands I can't have one without risking runtime type errors.

I agree. See my previous comments.

> Static typing that doesn't cover common use-cases is worse then useless. It gets in your way.

I agree. Fortunately Go's static typing covers the most common use cases. If your primary deliverable is typesafe tree algorithms, Go might not be for you.