Back to home

Setting up the testBinary Search Tree implementationRunning Tests
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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 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.

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 .

Related articles


1,200+ PEOPLE ALREADY JOINED ❤️️

Get fresh posts + news direct to your inbox.

No spam. We only send you relevant content.