main.go

package main

import (
	"fmt"
	"strings"
)

const (
	EQ = 0
	GT = -1
	LT = 1
)

type Node struct {
	Key   string
	Val   interface{}
	Left  *Node
	Right *Node
}

func (n *Node) DFSFind(key string) (interface{}, error) {
	switch strings.Compare(key, n.Key) {
	case EQ:
		return n.Val, nil
	case GT:
		if n.Right == nil {
			return nil, nil
		}

		return n.Right.DFSFind(key)
	case LT:
		if n.Left == nil {
			return nil, nil
		}

		return n.Left.DFSFind(key)
	default:
		return nil, fmt.Errorf("Unexpected result from strings.compare")
	}
}

func (r *Node) BFSFind(key string) (interface{}, error) {
	q := []*Node{r}

	for len(q) > 0 {
		n := q[0]
		q = q[1:]

		if n.Key == key {
			return n.Val, nil
		}

		if n.Left != nil {
			q = append(q, n.Left)
		}

		if n.Right != nil {
			q = append(q, n.Right)
		}
	}

	return nil, nil
}

func (n *Node) Print() {
	if n.Right != nil {
		n.Right.Print()
	}

	fmt.Printf("%s: %v\n", n.Key, n.Val)

	if n.Left != nil {
		n.Left.Print()
	}
}

func (n *Node) Insert(key string, val interface{}) error {
	switch strings.Compare(key, n.Key) {
	case EQ:
		n.Val = val
		return nil
	case GT:
		if n.Right == nil {
			n.Right = &Node{
				Key: key,
				Val: val,
			}
		} else {
			return n.Right.Insert(key, val)
		}
	case LT:
		if n.Left == nil {
			n.Left = &Node{
				Key: key,
				Val: val,
			}
		} else {
			return n.Left.Insert(key, val)
		}
	}

	return fmt.Errorf("Unexpected result from strings.compare")
}