Binary search tree implementation in golang

Question

I have started dabbling with golang. I wrote up a binary search tree implementation. I was wondering if there is a cleaner way. Here is my implementation:

type BNode struct {
    left  *BNode
    right *BNode
    data  int64
}

func insert(n **BNode, data int64) {
    if *n == nil {
        (*n) = &BNode{data: data, left: nil, right: nil}
    } else {
        if data <= (*n).data {
            insert(&(*n).left, data)
        } else {
            insert(&(*n).right, data)
        }
    }
}

I don't particularly like &(*n).right, is there syntax better than this? Something like &(n->right)

client code looks like:

var root *BNode = nil
insert(&root, 42)
insert(&root, 2)
insert(&root, -2)
insert(&root, 97)`

Answer 1

Some quick remarks:

• The type BNode is public, but the insert function isn't. This is quite strange.
• insert(null, 0) causes a panic. That's no good.
• &BNode{data: data, left: nil, right: nil} can be just &BNode{data: data} since the default value for a pointer is null.
• How would someone use a tree once you've added members to it? I'm guessing you have more functions than just insert, so would be good to share these as well.

You may want to have a separate type for the tree (that just contains a root) - this is a clean way of handling the empty tree case. In addition, insert seems more suitable as a method rather than a function, bringing the final result to something like this:

type BTree struct {
    root  *node
}

type node struct {
    left  *node
    right *node
    data  int64
}

func (t *BTree) Insert(data int64) {
    if t.root == nil {
        t.root = &node{data: data}
    } else {
        t.root.insert(data)
    }
}

func (n *node) insert(data int64) {
    if data <= n.data {
        if n.left == nil {
            n.left = &node{data: data}
        } else {
            n.left.insert(data)
        }
    } else {
        if n.right == nil {
            n.right = &node{data: data}
        } else {
            n.right.insert(data)
        }
    }
}

Usage:

var tree BTree
tree.insert(50)