Generics in Go, insert in a Binary Tree

First release of the implemetation of Generics is ready to use with Go 1.18. And without going into much discussion, I would like to say that with generics is a feature for implementing clean and reusable code.

Photo by Chinmay Bhattar on Unsplash

This article is a friendly explanation of the Generics implementation in Go, specifically by inserting nodes into a binary tree.

Placeholder T

The generic type, in this case the character T , is used as the type of a value. This generic could be int or string , we would know the specific type until the type is instantiated with an explicit one.

For now I am going to use a structure like the following:

type BinaryNode[T NumberType] struct {
    value T
    left  *BinaryNode[T]
    right *BinaryNode[T]
}
type BinaryTree[T NumberType] struct {
    root *BinaryNode[T]
}

T could be any type of NumberType defined. The type is known so we can trust allways the final result, no extra checks like with an interface{} . With Generics, if the type is wrong the code will not compile’ also we should see an alert in case of mixing types.

type NumberType interface {
    int32 | int64 | float32 | float64 // Go 1.18 embedded interface
}

No interface{} was used, nor any check of the type of T, just have to return the value of the type.

func (n *BinaryNode[T]) getValue() T {
    return n.value
}

That's it, now the binary tree can be created. You can be sure that the first tree will only accept int64, while the second treeFloat will accept float64 ; mixing types will prevent compilation.

func main() {
    tree := &BinaryTree[int64]{}
    tree.InsertNode(BinaryNode[int64]{value: 11})
    treeFloat := &BinaryTree[float64]{}
    treeFloat.InsertNode(BinaryNode[float64]{value: 11.11})
}

Here I leave how to insert new nodes, only one function remains pending to print the final tree and one to insert values in existing Nodes.

func (t *BinaryTree[T]) InsertNode(n BinaryNode[T]) *BinaryTree[T] {
    if t.root == nil {
        t.root = &BinaryNode[T]{value: n.getValue()}
    } else {
        t.root.insert(n.getValue())
    }
    return t
}

References:

• Complete example: generics.go
• Getting started with generics