We have a trie that stores set of integer slices. We want an iterator over its items. What we do here is have one goroutine to walk over the trie and send the items over channel. Other goroutine pulls the items from the channel and prints them out. My mental image of this is one gopher jumping around a tree and throwing mangoes back at his friend on the ground.

To balance the tree CLRS implementation rotates the subtrees. The functional implementations rewrites the tree [1,2]. Thinking in terms of rewriting instead of rotating feels like looking at the problem in a proper coordinate system. My implementation here is translation of Matt Might’s Haskell code in go. The generics syntax is easy on eyes. I like it. References The missing method: Deleting from Okasaki’s red-black trees by Matt Might Red-Black Trees in a Functional Setting by Okasaki The Next Step for Generics by Ian Lance Taylor and Robert Griesemer Code Playground link