2
\$\begingroup\$

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)`
\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.