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