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 &amp;&amp; *r.value == i {
        return &amp;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 = &amp;n
            return
        }

        if *pointer.value == n {
            return
        } else if *pointer.value &lt; n {
            if pointer.left != nil {
                pointer = pointer.left
            } else {
                pointer.left = &amp;SearchTree{&amp;n, nil, nil}
                return
            }
        } else {
            if pointer.right != nil {
                pointer = pointer.right
            } else {
                pointer.right = &amp;SearchTree{&amp;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)

        if err != nil {
            con.Close()
            return
        }

        cmdTxt := string(buffer[:numBytes])

        n, err := strconv.Atoi(cmdTxt[1:numBytes])

        if err == nil {
            fmt.Println(n)
            switch (cmdTxt[0]) {
            case 'g':
                if data.Contains(n) {
                    con.Write([]byte{6})
                } else {
                    con.Write([]byte{25})
                }
            case 's':
                data.Add(n)
                con.Write([]byte{6})
            }

        }

    }
}

func startServer() {
    ln, err := net.ListenTCP("tcp", generateAddr())

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

    for {
        fmt.Println("wait for connection")

        conn, err := ln.Accept()
        if err == nil {
            go handleConnection(conn)
        }

    }
}

func main() {
    startServer()
}
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 &lt; i {
        if node.left == nil {
            return nil
        }
        return node.left.getNode(i)
    }
    else if i &lt; 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 &lt; i {
        if node.left == nil {
            return &amp;node.left
        }
        return node.left.getNode(i)
    } else if i &lt; node.value {
        if node.right == nil {
            return &amp;node.right
        }
        return node.right.getNode(i)
    }
    return &amp;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 = &amp;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 &amp;BinaryTree { nil }
}

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

func (node *node) getNode(i int) **node {
    if node.value &lt; i {
        if node.left == nil {
            return &amp;node.left
        }
        return node.left.getNode(i)
    } else if i &lt; node.value {
        if node.right == nil {
            return &amp;node.right
        }
        return node.right.getNode(i)
    }
    return &amp;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 = &amp;node{n, nil, nil}
        return true
    }
    target := tree.root.getNode(n)
    if *target == nil {
        *target = &amp;node{n, nil, nil}
        return true
    }
    return false
}


(see it live on ideone)