Go Data Structures: Binary Search Tree
By Flavio Copes
Learn how the binary search tree works and how to implement it in Go, with Insert, Search, Remove and in-order, pre-order and post-order traversals.
A tree is a representation of a hierarchical structure. It’s easy to imagine a tree by thinking about a family genealogy tree.
Like a hash table or a graph, is a non-sequential data structure.
A binary tree is a tree where every node has max 2 children.
A binary search tree has the property of the left node having a value less than the value on the right node.
This is what we’ll build in this article. It’s a very useful data structure for efficient storing and indexing of data, and data retrieval.
The tree is generic over the value stored in each node (BinarySearchTree[T any]), using Go type parameters, so it needs Go 1.18 or later. The sort key stays an int to keep comparisons simple.
This post is part of my Go data structures series. The set is a smaller example of the same approach, if you want to start there.
Terminology
Root: the level 0 of the tree
Child: each node of the tree that’s not the root
Internal node: each node with at least a child
Leaf: each node that has no children
Subtree: the set of node with a certain node as root
Preliminary info
A binary search tree data structure will expose those methods:
Insert(key, value)inserts the value in the tree underkeySearch(key)returns true if a node with that key existsInOrderTraverse()visits all nodes with in-order traversingPreOrderTraverse()visits all nodes with pre-order traversingPostOrderTraverse()visits all nodes with post-order traversingMin()returns the value with the min key stored in the treeMax()returns the value with the max key stored in the treeRemove(key)removes the node with that key from the treeString()prints a CLI readable rendering of the tree
I define each node as
// Node a single node that composes the tree
type Node[T any] struct {
key int
value T
left *Node[T]
right *Node[T]
}The key value allows to use any kind of value type, and use a separate integer for calculating the correct place.
Inserting an item into a tree requires the use of recursion, since we need to find the correct place for it. The rule is, if the key of the node is < than the current node tree, we put it as the left child, if there is no left child. Otherwise, we recalculate the position by using the left child as the base node. Same goes for the right child.
Traversing is the process of navigating the tree, and we implement 3 ways to do it, since there are 3 different approaches. Taken this binary search tree:
this is how we could traverse it:
- in-order: we visit all nodes by following the smallest link until we find the left-most leaf, then processes the leaf and moves to other nodes by going into the next smallest key value linked to the current one. In the above picture:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 - pre-order: before visiting the children, this approach visits the node first. In the above picture:
8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 11 - post-order: we find the smallest leaf (the left-most one), then processes the sibling and then the parent node, then goes to the next subtree, and navigates up the parent. In the above picture:
1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8
The String method, used in the tests to have a visual feedback on the methods, will print the above tree as
------------------------------------------------
---[ 1
---[ 2
---[ 3
---[ 4
---[ 5
---[ 6
---[ 7
---[ 8
---[ 9
---[ 10
---[ 11
------------------------------------------------Implementation
// Package binarysearchtree creates a BinarySearchTree data structure
package binarysearchtree
import (
"fmt"
"sync"
)
// Node a single node that composes the tree
type Node[T any] struct {
key int
value T
left *Node[T]
right *Node[T]
}
// BinarySearchTree the binary search tree of values
type BinarySearchTree[T any] struct {
root *Node[T]
lock sync.RWMutex
}
// Insert inserts the value under key in the tree
func (bst *BinarySearchTree[T]) Insert(key int, value T) {
bst.lock.Lock()
defer bst.lock.Unlock()
n := &Node[T]{key, value, nil, nil}
if bst.root == nil {
bst.root = n
} else {
insertNode(bst.root, n)
}
}
// internal function to find the correct place for a node in a tree
func insertNode[T any](node, newNode *Node[T]) {
if newNode.key < node.key {
if node.left == nil {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
if node.right == nil {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
// InOrderTraverse visits all nodes with in-order traversing
func (bst *BinarySearchTree[T]) InOrderTraverse(f func(T)) {
bst.lock.RLock()
defer bst.lock.RUnlock()
inOrderTraverse(bst.root, f)
}
// internal recursive function to traverse in order
func inOrderTraverse[T any](n *Node[T], f func(T)) {
if n != nil {
inOrderTraverse(n.left, f)
f(n.value)
inOrderTraverse(n.right, f)
}
}
// PreOrderTraverse visits all nodes with pre-order traversing
func (bst *BinarySearchTree[T]) PreOrderTraverse(f func(T)) {
bst.lock.Lock()
defer bst.lock.Unlock()
preOrderTraverse(bst.root, f)
}
// internal recursive function to traverse pre order
func preOrderTraverse[T any](n *Node[T], f func(T)) {
if n != nil {
f(n.value)
preOrderTraverse(n.left, f)
preOrderTraverse(n.right, f)
}
}
// PostOrderTraverse visits all nodes with post-order traversing
func (bst *BinarySearchTree[T]) PostOrderTraverse(f func(T)) {
bst.lock.Lock()
defer bst.lock.Unlock()
postOrderTraverse(bst.root, f)
}
// internal recursive function to traverse post order
func postOrderTraverse[T any](n *Node[T], f func(T)) {
if n != nil {
postOrderTraverse(n.left, f)
postOrderTraverse(n.right, f)
f(n.value)
}
}
// Min returns a pointer to the value with min key stored in the tree
func (bst *BinarySearchTree[T]) Min() *T {
bst.lock.RLock()
defer bst.lock.RUnlock()
n := bst.root
if n == nil {
return nil
}
for {
if n.left == nil {
return &n.value
}
n = n.left
}
}
// Max returns a pointer to the value with max key stored in the tree
func (bst *BinarySearchTree[T]) Max() *T {
bst.lock.RLock()
defer bst.lock.RUnlock()
n := bst.root
if n == nil {
return nil
}
for {
if n.right == nil {
return &n.value
}
n = n.right
}
}
// Search returns true if a node with that key exists in the tree
func (bst *BinarySearchTree[T]) Search(key int) bool {
bst.lock.RLock()
defer bst.lock.RUnlock()
return search(bst.root, key)
}
// internal recursive function to search an item in the tree
func search[T any](n *Node[T], key int) bool {
if n == nil {
return false
}
if key < n.key {
return search(n.left, key)
}
if key > n.key {
return search(n.right, key)
}
return true
}
// Remove removes the node with key `key` from the tree
func (bst *BinarySearchTree[T]) Remove(key int) {
bst.lock.Lock()
defer bst.lock.Unlock()
bst.root = remove(bst.root, key)
}
// internal recursive function to remove an item
func remove[T any](node *Node[T], key int) *Node[T] {
if node == nil {
return nil
}
if key < node.key {
node.left = remove(node.left, key)
return node
}
if key > node.key {
node.right = remove(node.right, key)
return node
}
// key == node.key
if node.left == nil && node.right == nil {
return nil
}
if node.left == nil {
return node.right
}
if node.right == nil {
return node.left
}
leftmostrightside := node.right
for {
//find smallest value on the right side
if leftmostrightside != nil && leftmostrightside.left != nil {
leftmostrightside = leftmostrightside.left
} else {
break
}
}
node.key, node.value = leftmostrightside.key, leftmostrightside.value
node.right = remove(node.right, node.key)
return node
}
// String prints a visual representation of the tree
func (bst *BinarySearchTree[T]) String() {
bst.lock.Lock()
defer bst.lock.Unlock()
fmt.Println("------------------------------------------------")
stringify(bst.root, 0)
fmt.Println("------------------------------------------------")
}
// internal recursive function to print a tree
func stringify[T any](n *Node[T], level int) {
if n != nil {
format := ""
for i := 0; i < level; i++ {
format += " "
}
format += "---[ "
level++
stringify(n.left, level)
fmt.Printf(format+"%d\n", n.key)
stringify(n.right, level)
}
}You pick the value type when you create the tree:
bst := BinarySearchTree[string]{}
bst.Insert(8, "8")Notice that Remove() assigns the result of the recursive remove() call back to bst.root. Without that assignment, removing a root that has one child or none would leave bst.root pointing at the old node.
Tests
The tests describe the usage of the above implementation.
package binarysearchtree
import (
"testing"
)
var bst BinarySearchTree[string]
func fillTree(bst *BinarySearchTree[string]) {
bst.Insert(8, "8")
bst.Insert(4, "4")
bst.Insert(10, "10")
bst.Insert(2, "2")
bst.Insert(6, "6")
bst.Insert(1, "1")
bst.Insert(3, "3")
bst.Insert(5, "5")
bst.Insert(7, "7")
bst.Insert(9, "9")
}
func TestInsert(t *testing.T) {
fillTree(&bst)
bst.String()
bst.Insert(11, "11")
bst.String()
}
// isSameSlice returns true if the 2 slices are identical
func isSameSlice(a, b []string) bool {
if a == nil && b == nil {
return true
}
if a == nil || b == nil {
return false
}
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
func TestInOrderTraverse(t *testing.T) {
var result []string
bst.InOrderTraverse(func(i string) {
result = append(result, i)
})
if !isSameSlice(result, []string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11"}) {
t.Errorf("Traversal order incorrect, got %v", result)
}
}
func TestPreOrderTraverse(t *testing.T) {
var result []string
bst.PreOrderTraverse(func(i string) {
result = append(result, i)
})
if !isSameSlice(result, []string{"8", "4", "2", "1", "3", "6", "5", "7", "10", "9", "11"}) {
t.Errorf("Traversal order incorrect, got %v instead of %v", result, []string{"8", "4", "2", "1", "3", "6", "5", "7", "10", "9", "11"})
}
}
func TestPostOrderTraverse(t *testing.T) {
var result []string
bst.PostOrderTraverse(func(i string) {
result = append(result, i)
})
if !isSameSlice(result, []string{"1", "3", "2", "5", "7", "6", "4", "9", "11", "10", "8"}) {
t.Errorf("Traversal order incorrect, got %v instead of %v", result, []string{"1", "3", "2", "5", "7", "6", "4", "9", "11", "10", "8"})
}
}
func TestMin(t *testing.T) {
if *bst.Min() != "1" {
t.Errorf("min should be 1")
}
}
func TestMax(t *testing.T) {
if *bst.Max() != "11" {
t.Errorf("max should be 11")
}
}
func TestSearch(t *testing.T) {
if !bst.Search(1) || !bst.Search(8) || !bst.Search(11) {
t.Errorf("search not working")
}
}
func TestRemove(t *testing.T) {
bst.Remove(1)
if *bst.Min() != "2" {
t.Errorf("min should be 2")
}
}Want me to talk about your product? You can sponsor this site.