Number database using binary trees

This is a review of your binary tree implementation. I suppose it works, and it doesn't violate any major Go idioms. However, your algorithm for getNode sucks (\$O(n)\$ complexity), and there are a few minor WTFs.

I fail to understand why your SearchTree struct contains a value *int. Your design has no way for a user to get the value out of the tree, and changing the value would destroy the sorting. All you ever do is get a pointer to an argument (which was passed by value…), and then do annoying if value != nil tests. All of that is unnecessary once you use a simple value int.

As mentioned above, your getNode() is weird: Unless the current node contains the value, you recurse into both the left and right subtree. Since you insert the values in a sorted order, we can use the binary tree as an actual binary tree. The function then simplifies to:

func (node *SearchTree) getNode(i int) *SearchTree {
    if node.value < i {
        if node.left == nil {
            return nil
        }
        return node.left.getNode(i)
    }
    else if i < node.value {
        if node.right == nil {
            return nil
        }
        return node.right.getNode(i)
    }
    else {
        return node
    }
}

I also renamed the receiver argument from r to the less cryptic node, and changed the receiver type to *SearchTree. Previously, your function took a tree by value (i.e. copy), then returned a pointer to that copy, which appears to be a bit backwards.

Actually, we can use the same getNode() function for both search and insertion with a few variations. To do this, we return a pointer to the .left or .right entry, which is itself a pointer. We guarantee that the returned pointer will never be nil, and that it will be a pointer to nil if no element was found. Only if it points to nil will that pointer will be writable.

func (node *SearchTree) getNode(i int) **SearchTree {
    if node.value < i {
        if node.left == nil {
            return &node.left
        }
        return node.left.getNode(i)
    } else if i < node.value {
        if node.right == nil {
            return &node.right
        }
        return node.right.getNode(i)
    }
    return &node // not nil, not writable
}

func (node *SearchTree) Contains(n int) bool {
    return *(node.getNode(n)) != nil
}

// returns true if the tree was mutated as a result,
// and false if the number was already present
func (node *SearchTree) Add(n int) bool {
    target := node.getNode(n)
    if *target == nil {
        *target = &SearchTree{n, nil, nil}
        return true
    }
    return false
}

This double pointer may seem a bit jarring since we're already using one level of pointers. However, we want a pointer to that field in the parent node, which merely happens to contain a pointer type itself.

There is a remaining problem with your tree. Right now, declaring a variable of type SearchTree will assign a default value, which is a struct with all members assigned their default values – nil for pointers and 0 for integers. However, this means that the following code will always evaluate to true:

val empty SearchTree
empty.Contains(0) // true, oops!

The solution is to create a wrapper type containing a pointer to the search tree for the public interface. What was previously called SearchTree, we rename to node, and create type BinaryTree struct { root *node }. While not necessary, I'd also provide an explicit constructor NewBinaryTree().

This is the code I ended up with:

type BinaryTree struct {
    root *node
}

func NewBinaryTree() *BinaryTree {
    return &BinaryTree { nil }
}

type node struct {
    value int
    left, right *node
}

func (node *node) getNode(i int) **node {
    if node.value < i {
        if node.left == nil {
            return &node.left
        }
        return node.left.getNode(i)
    } else if i < node.value {
        if node.right == nil {
            return &node.right
        }
        return node.right.getNode(i)
    }
    return &node // not nil, not writable
}

func (tree *BinaryTree) Contains(n int) bool {
    root := tree.root
    if root == nil {
        return false
    }
    return *(root.getNode(n)) != nil
}

// returns true if the tree was mutated as a result,
// and false if the number was already present
func (tree *BinaryTree) Add(n int) bool {
    if tree.root == nil {
        tree.root = &node{n, nil, nil}
        return true
    }
    target := tree.root.getNode(n)
    if *target == nil {
        *target = &node{n, nil, nil}
        return true
    }
    return false
}

(see it live on ideone)