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

• ← Process Description And Control
• Moving To Melbourne →