Binary tree and some generic tricks with golang

[Aerosol]

It is quite easy to create binary tree implementation with Go programming language, but it's not clearly for the first view how to make it generic. I think most of us know what is it Binary tree, so I will no explain it here, you can find in the Internet. Let's try to implement binary tree. As you can read about I want to implement generic binary try, so I don't want to make binary tree for some concrete type like int, string and etc... it must generic and be able to work with any data types. It is not a problem to make it generic, because we have {}interface type in Golang. interface{} type means something like any type. That's way you free to do something like this:

var myString interface{} = "myString"
var myInt interface{} = 0

Ok, we have interface{} type for any type. Let's create binary tree structure now:

type BinaryTree struct {
    node interface{}
    left  *BinaryTree
    right *BinaryTree
}

We can see here that binary tree consist from node and pointers to left and right nodes:

Now need to create initialization helper for our binary tree which will return empty binary tree to user:

func New() *BinaryTree {
    tree := &BinaryTree{}
    tree.node = nil
    return tree
}

Ok, now we have binary tree data structure and some code for it's initialization. Let's go to the most interesting part. Now we create Insert function. It will get 1 parameter, some data with interface{} type and insert new node to the our binary tree. How insert works for binary tree: It get new node and tree and check if this tree is empty it creates new first node with this data. If tree is not empty, it compares new node data with current node value and if it is greater it goes recursively to right branch, and if it is smaller it goes to left node in the same way. Implementation of this is following:

func (tree *BinaryTree) Insert(value interface{}) {
    if tree.node == nil {
        tree.node = value
        tree.right = New()
        tree.left  = New()
        return
    } else {
        if value < tree.node {
            tree.left.Insert(value)
        } else {
            tree.right.Insert(value)
        }
    }
}

Very simple implementation of inserting but it will not work If we try to compile our code, we'll get error that: < operator not defined for interface. From the point of logic it is properly behaviour. Really, interface{} means any type, so golang doesn't know what's type will be there and how to compare two values of this type. Actually we can pass and int and string and MyCustomType instead interface{}. How to be with this? If we will look how another programming languages solve this problem, we will find something interesting. Let's look to Haskell for example: There is Ord type class which provides behaviour for <,> and other function for comparing data. Binary tree in Haskell looks like:

data Tree a = Empty | Node a (Tree a) (Tree a)

Practically it looks almost like golang implementation but with another syntax. We have current node and recursively defined left and right trees. We can see a here, it is like interface{} type in golang. We just can make instance of Ord for Tree and tell Haskell compiler how to use <, > and other operators for tree. There is method to do this in golang like in Haskell. Let's update our binary tree structure and add one function there:

type BinaryTree struct {
    node interface{}
    left  *BinaryTree
    right *BinaryTree
    lessFun Comparable
}

type Comparable func (c1 interface{}, c2 interface{}) bool

You can see that we had add new field: lessFun which has functional type which gets two arguments with interface{} type and returns bool. How it help us? Before initialization of new binary tree, user will create function with two interface{} and implement comparing of this two arguments there. if first argument smaller than second it will returns true, and false in against way. Usually user knows what's type will be in binary tree and user must know how compare his types. After defining this function need to pass it to New function, so it will be like this:

func New(compareFun Comparable) *BinaryTree {
    tree := &BinaryTree{}
    tree.node = nil
    tree.lessFun = compareFun
    return tree
}

And now we can write insert function:

func (tree *BinaryTree) Insert(value interface{}) {
    if tree.node == nil {
        tree.node = value
        tree.right = New(tree.lessFun)
        tree.left  = New(tree.lessFun)
        return
    } else {
        if tree.lessFun(value, tree.node) == true {
            tree.left.Insert(value)
        } else {
            tree.right.Insert(value)
        }
    }
}

Insert function compares node and new node with lessFun function, so it already knows how to compare data with certain types. For example we want to create binary tree for int, it will be:

func compare(x interface{}, y interface{}) bool {
    if x.(int) < y.(int) {
        return true
    } else {
        return false
    }
}

func main(){
    tree := New(compare)

    tree.Insert(1)
    tree.Insert(2)
    tree.Insert(3)
}

Here is compare function which gets two arguments with interface{} type and compares it resulting to int type. Than we create new binary tree with New function and pass our compare function to it. And tries to insert some integer numbers to binary tree. It works perfectly, because current binary tree already knows how to compare nodes with lessFun.

Full source code of binary tree you can find - here.

Source