Binary Search Tree in Go (Golang)
package mainimport (
"fmt"
)type Node struct {
value int
left *Node
right *Node
}
type Tree struct {
root *Node
}func (t *Tree) reset() {
t.root = nil
}
func (t *Tree) insert(value int) {
t.insertRec(t.root, value)
}
func (t *Tree) insertRec(node *Node, value int) *Node {
if t.root == nil {
t.root = &Node{
value: value,
}
return t.root
}
if node == nil {
return &Node{value: value}
}
if value <= node.value {
node.left = t.insertRec(node.left, value)
}
if value > node.value {
node.right = t.insertRec(node.right, value)
}
return node}func (t *Tree) find(value int) error {
node := t.findRec(t.root, value)
if node == nil {
return fmt.Errorf("Value %d not find in tree", value)
}
return nil
}
func (t *Tree) findRec(node *Node, value int) *Node {
if node == nil {
return nil
}
if node.value == value {
return node
}
if value < node.value {
return t.findRec(node.left, value)
}
return t.findRec(node.right, value)
}
func (t *Tree) inorder() {
t.inorderRec(t.root)
}
func (t *Tree) inorderRec(node *Node) {
if node != nil {
t.inorderRec(node.left)
fmt.Println(node.value)
t.inorderRec(node.right)
}
}
func main() {
tree := &Tree{}
eg := []int{2, 4, 5, 6, 7, 8, 8, 5}
for _, val := range eg {
tree.insert(val)
}
fmt.Println("printing inorder")
tree.inorder()
tree.reset()
eg = []int{4, 5, 7, 6, -1, 99, 5}
for _, val := range eg {
tree.insert(val)
}
fmt.Printf("\nPrinting Inorder:\n")
tree.inorder()
fmt.Printf("\nFinding Values:\n")
err := tree.find(2)
if err != nil {
fmt.Printf("Value %d Not Found\n", 2)
} else {
fmt.Printf("Value %d Found\n", 2)
}
err = tree.find(6)
if err != nil {
fmt.Printf("Value %d Not Found\n", 6)
} else {
fmt.Printf("Value %d Found\n", 6)
}
err = tree.find(5)
if err != nil {
fmt.Printf("Value %d Not Found\n", 5)
} else {
fmt.Printf("Value %d Found\n", 5)
}
err = tree.find(1)
if err != nil {
fmt.Printf("Value %d Not Found\n", 1)
} else {
fmt.Printf("Value %d Found\n", 1)
}
}
Output:
printing inorder
2
4
5
5
6
7
8
8
Printing Inorder:
-1
4
5
5
6
7
99
Finding Values:
Value 2 Not Found
Value 6 Found
Value 5 Found
Value 1 Not Found