Number database using binary trees

I recently got interested in Go and wrote a database server which uses a binary tree for data storage for fun. As I have no prior experience in Go, I'd like to gather a bit feedback on my code and would like to know how I can improve/optimize it.

File: BinaryTree.go

package BinaryTree

//import "fmt"

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

func (r SearchTree) getNode(i int) *SearchTree {

    if r.value != nil && *r.value == i {
        return &r
    }

    if r.left != nil {
        ref := r.left.getNode(i)
        if ref != nil {
            return ref
        }
    }

    if r.right != nil {
        ref := r.right.getNode(i)
        if ref != nil {
            return ref
        }
    }

    return nil
}

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

func (r *SearchTree) Add(n int) {
    pointer := r

    for {

        if pointer.value == nil {
            pointer.value = &n
            return
        }

        if *pointer.value == n {
            return
        } else if *pointer.value < n {
            if pointer.left != nil {
                pointer = pointer.left
            } else {
                pointer.left = &SearchTree{&n, nil, nil}
                return
            }
        } else {
            if pointer.right != nil {
                pointer = pointer.right
            } else {
                pointer.right = &SearchTree{&n, nil, nil}
                return
            }
        }

    }
}

File: server.go

```
package main

import (
"fmt"
"net"
"log"
"BinaryTree"
"strconv"
)

var data BinaryTree.SearchTree

func generateAddr() *net.TCPAddr {
addr, err := net.ResolveTCPAddr("tcp", "localhost:19800")

if err != nil {
log.Fatal(err)
}

return addr
}

func handleConnection(con net.Conn) {
fmt.Println("handling connection")

buffer := make([]byte, 256)
for {
numBytes, err := con.Read(buffer)

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)

StackExchange Code Review Q#71239, answer score: 5