Go Binary Search Trees
May 20, 2019
Binary Search Tree implementation with Golang.
Setting up the test
Set up binary_search_trees_test.go
with the following file to test inserts, retrievals and validations:
package binarysearchtree
import "testing"
func TestBinarySearchTreeInsert(t *testing.T) {
n := &Node{data: 5}
b := BST{root: n}
b.root.lock.Lock()
b.root.insert(1)
b.root.lock.Unlock()
b.root.lock.Lock()
b.root.insert(8)
b.root.lock.Unlock()
b.root.lock.Lock()
b.root.insert(3)
b.root.lock.Unlock()
expected := b.root.left.data
observed := 1
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
expected = b.root.right.data
observed = 8
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
expected = b.root.left.right.data
observed = 3
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
}
func TestBinarySearchTreeContains(t *testing.T) {
n := &Node{data: 5}
b := BST{root: n}
b.root.lock.Lock()
b.root.insert(1)
b.root.lock.Unlock()
b.root.lock.Lock()
b.root.insert(8)
b.root.lock.Unlock()
b.root.lock.Lock()
b.root.insert(3)
b.root.lock.Unlock()
expected := b.root.contains(1)
observed := b.root.left
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
expected = b.root.contains(8)
observed = b.root.right
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
expected = b.root.contains(3)
observed = b.root.left.right
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
expected = b.root.contains(13)
observed = nil
if expected != observed {
t.Fatalf("BinarySearchTree()) = %d, want %d", observed, expected)
}
}
func TestBSTValidate(t *testing.T) {
n := &Node{data: 5}
b := BST{root: n}
b.root.lock.Lock()
b.root.insert(1)
b.root.lock.Unlock()
b.root.lock.Lock()
b.root.insert(8)
b.root.lock.Unlock()
b.root.lock.Lock()
b.root.insert(3)
b.root.lock.Unlock()
observed := b.root.validate(nil, nil)
expected := true
if expected != observed {
t.Fatalf("BinarySearchTree()) = %t, want %t", observed, expected)
}
}
Binary Search Tree implementation
package binarysearchtree
import (
"sync"
)
// Node defines a tree node hosting data
type Node struct {
data int
left *Node
right *Node
lock sync.Mutex
}
// BST Binary Search Tree
type BST struct {
root *Node
}
func (n *Node) insert(data int) {
if data < (*n).data && (*n).left != nil {
(*n).left.insert(data)
} else if data < (*n).data {
node := &Node{}
node.data = data
(*n).left = node
} else if data > (*n).data && (*n).right != nil {
(*n).right.insert(data)
} else if data > (*n).data {
node := &Node{}
node.data = data
(*n).right = node
}
}
func (n *Node) contains(data int) *Node {
if n.data == data {
return n
} else if data < n.data && n.left != nil {
return n.left.contains(data)
} else if data > n.data && n.right != nil {
return n.right.contains(data)
}
return nil
}
func (n *Node) validate(min *int, max *int) bool {
if min != nil && n.data < *min {
return false
} else if max != nil && n.data > *max {
return false
} else if n.left != nil && !n.left.validate(min, &n.data) {
return false
} else if n.right != nil && !n.right.validate(&n.data, max) {
return false
}
return true
}
Running Tests
In the directory, run go test
.
Related Articles
A personal blog on all things of interest. Written by Dennis O'Keeffe, Follow me on Twitter