Generic Binary Tree

I was wondering if any of the members know a proper way to implement a generic binary tree in GoLang?

I tried it with a Btree interface and two struct’s empty and node which implement the Btree interface and it seems to work until I need function signatures for the Btree interface which require additional generic parameters. My solution. Just move the functionality out the Btree interface and create generic functions which take a Btree… Here’s the functionality I’m playing with:

btree.go

package btree

type Btree[T any] interface {
	isEmpty() bool
	Display(func(...any) (int, error))
	Add(T, func(T, T) int) Btree[T]
	Find(T, func(T, T) int) Btree[T]
	Filter(func(T) bool) Btree[T]
}
//moved Fold out Btree bc of extra generic parameter
func Fold[T any, U any](bt Btree[T], f func(U, T) U, acc U) U {
	if bt.isEmpty() {
		return acc
	} else {
		n := bt.(node[T])
		return Fold(n.right, f, Fold(n.left, f, f(acc, n.data)))
	}
}

func mapb_aux[T any, U any](acc *Btree[U], bt Btree[T], f func(T) U, c func(U, U) int) {
	if !bt.isEmpty() {
		n := bt.(node[T])
		mapb_aux(acc, n.left, f, c)
		*acc = (*acc).Add(f(n.data), c)
		mapb_aux(acc, n.right, f, c)
	}
}
//moved MapB out Btree bc of extra generic parameter
func MapB[T any, U any](bt Btree[T], f func(T) U, c func(U, U) int) Btree[U] {
	acc := CreateEmptyBtree[U]()
	mapb_aux(&acc, bt, f, c)
	return acc
}

func CreateEmptyBtree[T any]() Btree[T] {
	return empty[T]{}
}

empty.go

package btree

type empty[T any] struct{}

func (empty[T]) isEmpty() bool {
	return true
}

func (empty[T]) Display(f func(...any) (int, error)) {
	f("Empty")
}

func (e empty[T]) Add(data T, f func(T, T) int) Btree[T] {
	return node[T]{data, e, e}
}

func (e empty[T]) Find(_ T, f func(T, T) int) Btree[T] {
	return e
}

func (e empty[T]) Filter(_ func(T) bool) Btree[T] {
	return e
}

node.go

package btree

type node[T any] struct {
	data  T
	left  Btree[T]
	right Btree[T]
}

func (node[T]) isEmpty() bool {
	return false
}

func (n node[T]) Display(f func(...any) (int, error)) {
	n.left.Display(f)
	f(n.data)
	n.right.Display(f)
}

func (n node[T]) Add(data T, f func(T, T) int) Btree[T] {
	ans := f(n.data, data)
	if ans < 0 {
		return node[T]{n.data, n.left.Add(data, f), n.right}
	} else if ans > 0 {
		return node[T]{n.data, n.left, n.right.Add(data, f)}
	}
	return n
}

func (n node[T]) Find(data T, f func(T, T) int) Btree[T] {
	ans := f(n.data, data)
	if ans < 0 {
		return n.left.Find(data, f)
	} else if ans > 0 {
		return n.right.Find(data, f)
	}
	return n
}

func join_branches[T any](left, right Btree[T]) Btree[T] {
	if right.isEmpty() {
		return left
	}
	n := right.(node[T])
	return node[T]{n.data, join_branches(left, n.left), n.right}
}

func (n node[T]) Filter(f func(T) bool) Btree[T] {
	if f(n.data) {
		return join_branches(n.left, n.right).Filter(f)
	}
	return node[T]{n.data, n.left.Filter(f), n.right.Filter(f)}
}

main.go

package main

import (
	"fmt"
	"math/rand"
	btree "packs/MyPacks/Btree"
	"strconv"
	"time"
)

func createRandomIntSlice(s []int) []int {
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(s), func(i, j int) { s[i], s[j] = s[j], s[i] })
	return s
}

func compare_ints(i, j int) int {
	if i < j {
		return -1
	} else if i > j {
		return 1
	}
	return 0
}

func compare_strings(i, j string) int {
	if i < j {
		return -1
	} else if i > j {
		return 1
	}
	return 0
}

func main() {
	bt := btree.CreateEmptyBtree[int]()
	for _, e := range createRandomIntSlice([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) {
		bt = bt.Add(e, compare_ints)
	}
	bt.Display(fmt.Println)
	fmt.Println(bt)
	fmt.Println("\n\nFind")
	bt.Find(4, compare_ints).Display(fmt.Println)
	fmt.Println(bt.Find(4, compare_ints))
	fmt.Println("\n\nFilter")
	bt.Filter(func(i int) bool { return i%2 == 0 }).Display(fmt.Println)
	fmt.Println(bt.Filter(func(i int) bool { return i%2 == 0 }))
	fmt.Println("\n\nFold")
	fmt.Println(btree.Fold(bt, func(acc, e int) int { return acc + e }, 0))
	bts := btree.MapB(bt, func(i int) string { return strconv.Itoa(i) }, compare_strings)
	bts.Display(fmt.Println)
}

Is there any problems with creating a generic binary tree this way in GoLang?

Hi @G4143,

Why do you start with an interface? Why not making BTree a struct with methods?

Well if you use an interface to represent a Btree then you can have a node or an empty structure implement the Btree and then you can do away with pointers.

Ok, then I am perhaps not the right person to discuss this, because I have no problems with pointers.

(My approach to building a generic binary tree does use pointers, and I find the approach to be pretty much straightforward.)

Thus I am not sure if “doing away with pointers” is a strong enough reason to express a tree through an interface instead of using pointers. Interfaces are meant to be used for defining a common set of functions that can have multiple implementations (like, for example, io.Reader, with implementations in bufio, os, etc.).

This being said, I find your approach quite readable, even though the reason for using an interface here seems unusual.

Regarding Fold and MapB, since they require extra type parameters that are not related to the BTree, then maybe it’s just fine to have them live outside the interface. Consider these functions as auxiliary functions. They are a part of the btree package API anyway, and this fact alone makes them a part of the BTree functionality.

1 Like

Thank-you for posting your binary tree solution.

I’m think I may change my binary tree and have most of the functionality live outside of any interface or structure. Just experimenting right now and seeing what’s possible.

1 Like

I think I’ll leave it here with my latest pondering about generics and binary trees in GoLang.

This version has one good point… It really hides the implementation details.

btree.go

package btree

type Btree[T any] interface {
	isEmpty() bool
	get() (node[T], error)
	display(f func(...any) (int, error))
	add(T) Btree[T]
	find(T) Btree[T]
	filter(func(T) bool) Btree[T]
}

func CreateEmptyBtree[T any](compare func(T, T) int) Btree[T] {
	return empty[T]{compare}
}

func DisplayBtree[T any](bt Btree[T], f func(...any) (int, error)) {
	bt.display(f)
}

func AddDataBtree[T any](bt Btree[T], data T) Btree[T] {
	return bt.add(data)
}

func FindDataBtree[T any](bt Btree[T], data T) Btree[T] {
	return bt.find(data)
}

func FilterBtree[T any](bt Btree[T], filter func(T) bool) Btree[T] {
	return bt.filter(filter)
}

func mapBtree_aux[T, U any](acc *Btree[U], bt Btree[T], m_f func(T) U) {
	if !bt.isEmpty() {
		n, _ := bt.get()
		mapBtree_aux(acc, n.left, m_f)
		*acc = AddDataBtree(*acc, m_f(n.data))
		mapBtree_aux(acc, n.right, m_f)
	}
}

func MapBtree[T, U any](bt Btree[T], mapb func(T) U, compare func(U, U) int) Btree[U] {
	acc := CreateEmptyBtree(compare)
	mapBtree_aux(&acc, bt, mapb)
	return acc
}

func Fold[T, U any](bt Btree[T], f func(U, T) U, acc U) U {
	if bt.isEmpty() {
		return acc
	} else {
		n, _ := bt.get()
		return Fold(n.right, f, Fold(n.left, f, f(acc, n.data)))
	}
}

node.go

package btree

type node[T any] struct {
	data    T
	left    Btree[T]
	right   Btree[T]
	compare func(T, T) int
}

func (node[T]) isEmpty() bool {
	return false
}

func (n node[T]) get() (node[T], error) {
	return n, nil
}

func (n node[T]) display(f func(...any) (int, error)) {
	n.left.display(f)
	f(n.data)
	n.right.display(f)
}

func (n node[T]) add(data T) Btree[T] {
	ans := n.compare(n.data, data)
	if ans < 0 {
		return node[T]{n.data, n.left.add(data), n.right, n.compare}
	} else if ans > 0 {
		return node[T]{n.data, n.left, n.right.add(data), n.compare}
	}
	return n
}

func (n node[T]) find(data T) Btree[T] {
	ans := n.compare(n.data, data)
	if ans < 0 {
		return n.left.find(data)
	} else if ans > 0 {
		return n.right.find(data)
	}
	return n
}

func join_branches[T any](left, right Btree[T]) Btree[T] {
	if right.isEmpty() {
		return left
	}
	n, _ := right.get()
	return node[T]{n.data, join_branches(left, n.left), n.right, n.compare}
}

func (n node[T]) filter(f func(T) bool) Btree[T] {
	if f(n.data) {
		return join_branches(n.left, n.right).filter(f)
	}
	return node[T]{n.data, n.left.filter(f), n.right.filter(f), n.compare}
}

empty.go

package btree

import "errors"

type empty[T any] struct {
	compare func(T, T) int
}

func (empty[T]) isEmpty() bool {
	return true
}

func (empty[T]) get() (node[T], error) {
	var data node[T]
	return data, errors.New("Empty carries no data")
}

func (empty[T]) display(f func(...any) (int, error)) {
	f("Empty")
}

func (e empty[T]) add(data T) Btree[T] {
	return node[T]{data, e, e, e.compare}
}

func (e empty[T]) find(_ T) Btree[T] {
	return e
}

func (e empty[T]) filter(_ func(T) bool) Btree[T] {
	return e
}

main.go

package main

import (
	"fmt"
	"math/rand"
	btree "packs/MyPacks/Btree"
	"strconv"
	"time"
)

func compare_int(i, j int) int {
	if i < j {
		return -1
	} else if i > j {
		return 1
	}
	return 0
}

func compare_string(i, j string) int {
	if i < j {
		return 1
	} else if i > j {
		return -1
	}
	return 0
}

func createRandomIntSlice(s []int) []int {
	rand.Seed(time.Now().UnixNano())
	rand.Shuffle(len(s), func(i, j int) { s[i], s[j] = s[j], s[i] })
	return s
}

func main() {
	bt := btree.CreateEmptyBtree(compare_int)
	for _, e := range createRandomIntSlice([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) {
		bt = btree.AddDataBtree(bt, e)
	}
	btree.DisplayBtree(bt, fmt.Println)
	fmt.Println("\n\nFind 4")
	btree.DisplayBtree(btree.FindDataBtree(bt, 4), fmt.Println)
	fmt.Println("\n\nFilter even")
	btree.DisplayBtree(btree.FilterBtree(bt, func(i int) bool { return i%2 == 0 }), fmt.Println)
	fmt.Println("\n\nMap int to string")
	bts := btree.MapBtree(bt, strconv.Itoa, compare_string)
	btree.DisplayBtree(bts, fmt.Println)
	fmt.Println("\n\nFold")
	fmt.Println(btree.Fold(bt, func(acc, e int) int { return acc + e }, 0))
	fmt.Println("\n\nFold big test, fold btree into btree")
	bt2 := btree.CreateEmptyBtree(compare_int)
	for _, e := range createRandomIntSlice([]int{11, 12, 13, 14, 15, 16, 17, 18, 19, 20}) {
		bt2 = btree.AddDataBtree(bt2, e)
	}
	btf := btree.Fold(bt2, func(acc btree.Btree[int], e int) btree.Btree[int] { return btree.AddDataBtree(acc, e) }, bt)
	btree.DisplayBtree(btf, fmt.Println)
}

hi @G4143 ,

Your binary tree implementation is pretty good. The generics are used in the way they are supposed to, however it could still benefit from some small changes.

The main thing you have to keep in mind when implementing a data structure is how and where you code will be used. In this case, it will be packaged as a library and people will use it to insert and remove elements from it. You need to always ask yourself “how can I better help my users ?”, and here are my 2 cents:

  • specify that your code is not concurrency safe, both in the code and in the readme
  • add a lot of unit tests, at a minimum one for each corner case (difficult input) for every public method
  • add a benchmark for each public method (the methods of the Btree interface), and add its results in the readme
  • again, in the readme add an example (code) on how this data structure is intended to be used
  • add some fuzzy tests, to prove to your users that this code was tested on large random data (I am also experimenting with this, private message me for help on fuzzy tests)

As a rule of thumb, you want to spend more time brainstorming on “how can I better help my users ?” and planning, than the time it take to write the actual code.

Now getting to the practical aspects of your posted code:

  • you create var data node[T] in order to immediately return data, an alternative approach to create the zero value of a generic type is *new(node[T])

  • you have the empty struct, to define an empty binary tree; this is not needed, you should be able to use literally an empty object of type Btree

  • the node struct should not contain a left and right Btree fields, but instead a left an right node fields; the type node should not know that the type Btree exists

  • all methods of both node and Btree should have pointer receivers

  • the method node.display does a depth first search, and calls f(n.data) on every node it iterates on; a better name for it would be DFS, or DepthFirstSearch

  • instead of having a node.compare method, that compares two objects of type T, it would make sense to have node[T any] to be of type node[T constraints.Ordered], take a look at constraints package - golang.org/x/exp/constraints - pkg.go.dev ;

  • similarly, you can define you own Comparable interface, and have T by of type Comparable - this puts the responsibility for Compare on your users:

    type Comparable interface {
       Compare(other Comparable) int
    }
    
  • node’s filter and join_branches need better documentation (comments) and you cannot understand what they do without reading their code; as a rule of thumb, if you can understand what a method does by only reading its signature, you can get away without any comments

  • both filter and join_branches are recursive (this usually means they can be written more efficiently, and also that they will be costly for large data) and they reallocate memory (they duplicate the memory used for your node and its subtrees) ← maybe you can improve them a bit, from an algorithm perspective

  • when writing libraries, people will actually read your code, thus formatting is important. Use something like gofumpt (lots of linters enabled); also separate logical blocks of code using newlines (notice below that I added 2 newlines between these 3 logical block of codes: input validation, computing result, returning result):

    func join_branches[T any](left, right Btree[T]) Btree[T] {
        if right.isEmpty() {
           	return left
        }
    
        n, _ := right.get()
    
        return node[T]{n.data, join_branches(left, n.left), n.right, n.compare}
    }
    
  • the point above is more important than it looks, add newlines to all your methods

  • the node.find method does not need an else if command, instead go with this:

    func (n node[T]) find(data T) Btree[T] {
        ans := n.compare(n.data, data)
    
        if ans < 0 {
            return n.left.find(data)
        }
    
        if ans > 0 {
            return n.right.find(data)
        }
    
        return n
    }
    
  • the node.display method takes in a function parameter f: display(f func(...any) (int, error)); it makes more sense to change the definition of f to display(f func(T) (int, error)), as you will only call it with f(n.data)

  • the Btree interface should be private (and named just tree), and its methods public (their names starting with uppercase); this is because you want users to only import one thing from your package, namely a btree object; A bit complex: it is the interest of your users to define their own tree interface, and only call your package to obtain an object that implements their interface ← in this way, if you change your implementation (like rename one of the functions in your interface) it will do minimal damage to their existing code; read about the “Accept interfaces, return structs” principle of Golang

  • the CreateEmptyBtree method should be renamed to New, and it will return and empty object; the empty struct should be renamed to btree (and make all its methods have pointer receivers); thus you end up having method new.New() *btree, and it is the *btree object that implements the tree interface

  • rename functions DisplayBtree, AddDataBtree, FindDataBtree, FilterBtree to: Display, Add, Find and Filter. Make them be public methods of the btree struct (the btree struct is your current empty struct, rename that to btree)

  • what does Fold do ? it does DFS and calls f for each value it iterates through ? if so, you can simplify it by having a DFS method and f is a closure over a slice into which you add the value of each iterated node

  • function mapBtree_aux has an if to check if the tree is empty, that if should return right there; the pattern should be:

    method() {
         if condition {
              return
         }
    
         doStuff
    }
2 Likes

All good points but I was more concerned with what the type system+generics could do if I tried something a little off the beaten GoLang path. I’ll leave the library writing to someone who’s a little more talented.

Actually, I’m a little surprised at how accommodating GoLang’s type system is. For instance… Its easy to create a generic lazy sequence in GoLang.