Back to home

Go Binary Search Trees main image

Go Binary Search Trees

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.

Personal image

Dennis O'Keeffe

@dennisokeeffe92
  • Melbourne, Australia

Hi, I am a professional Software Engineer. Formerly of Culture Amp, UsabilityHub, Present Company and NightGuru.
I am currently working on workingoutloud.dev, Den Dribbles and LandPad .

1,200+ PEOPLE ALREADY JOINED ❤️️

Get fresh posts + news direct to your inbox.

No spam. We only send you relevant content.