Basic Binary Tree in Go

Question

As an exercise I have written a basic binary tree implementation in Go.

Tree struct:

type Tree struct {
    Key   *int
    Value interface{}
    Left  *Tree
    Right *Tree
}

func New() *Tree {
    return &Tree{}
}

It a annoys me a bit, that Key is a pointer, but this is needed at the moment, because I use nil as an indicator for an empty node, e.g. in Insert:

func (t *Tree) Insert(key int, value interface{}) {
    if t.Key == nil {
        t.Key = &key
        t.Value = value
        t.Left = New()
        t.Right = New()
    } else {
        if key == *t.Key {
            return
        }
        if key < *t.Key {
            t.Left.Insert(key, value)
        } else {
            t.Right.Insert(key, value)
        }
    }
}

The Search method does not look too bad, but the nil check still looks wrong:

func (t *Tree) Search(key int) *Tree {
    if t.Key == nil {
        return nil
    }
    if *t.Key == key {
        return t
    }
    if key < *t.Key {
        return t.Left.Search(key)
    } else {
        return t.Right.Search(key)
    }
}

Would this be idiomatic Go? Wouldn't it be better to forego nil checks, since

Hoare [...] described their invention [Nullable references] as a "billion dollar mistake".

From: http://en.wikipedia.org/wiki/Nullable_type

---

Full implementation: https://github.com/miku/arboretum/blob/2f3646d8483b5db249917921feedb9732754a7bf/bst/bst.go

Example usage: https://github.com/miku/arboretum/blob/2f3646d8483b5db249917921feedb9732754a7bf/examples/bst.go