Learning how to insert a new node and delete an existing node in a binary search tree with Go language.
Update: 2022/10/27. Use a more intuitive method to implement a node of binary search tree and introduce the search method. Besides, provide 2 methods to implement inorder traversal.
Update: 2023/08/03. Bug fixes in Delete(). When replacing the deleted node with the successor, we should update not only the value but also the key.
Update: 2023/09/12. Give some alternative methods to implement node insertion and then compare the performance of iterative insertion and recursive insertion.
What is a binary search tree?
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.
BST has some properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
Insert
Insert() inserts a given new node to the given tree. Let’s see its abstract data type.
// The abstract data type for binary search tree.
type BSTNode struct {
Key int
Val interface{}
left *BSTNode
right *BSTNode
}
type BST struct {
root *BSTNode
}If we have no root node, we must create a new node and set the new node as the root of the tree.
When inserting the new node, put the smaller node to the left part and the greater node to the right part.
In order to implement insert() method, we can modify the pointer that points to the new node. For example, see figure 2(d), if we want to add (Ruby, 154) to the tree, we can modify the member rightin (Hanamaru, 152). We can modify the value (hanamaru.right) by using its pointer (&hanamaru.right).
func (b *BST) Insert(n *BSTNode) {
// super is the pointer of the pointer
// that points to the new node
super := &b.root
for *super != nil {
if n.Key < (*super).Key {
super = &(*super).left
} else {
super = &(*super).right
}
}
*super = n
}The type of super at line 4 is **Node . It is a pointer of the pointer that points to the new node. We can modify the pointer that points to the new node by super.
There is an alternative way to implement insertion without using pointers. Pointers are more complex and less efficient to operate in Go and other common programming languages.
func (b *BST) Insert2(n *BSTNode) {
var parent *BSTNode
current := b.root
for current != nil {
parent = current
if n.Key < current.Key {
current = current.left
} else {
current = current.right
}
}
if parent != nil {
if parent.Key > n.Key {
parent.left = n
} else {
parent.right = n
}
} else {
b.root = n
}
}Node insertion can also be implemented recursively. Nevertheless, the recursive function consumes more memory to maintain a stack, making it usually less efficient than the iterative one.
func (b *BST) InsertRec(n *BSTNode) {
b.root = b.root.insertRec(n)
}
func (b *BSTNode) insertRec(n *BSTNode) *BSTNode {
if b == nil {
return n
}
if n.Key < b.Key {
b.left = b.left.insertRec(n)
} else if n.Key > b.Key {
b.right = b.right.insertRec(n)
}
return b
}We can simply compare the performance of these functions by continuously inserting nodes.
func generateData(size int) []int {
r := rand.New(rand.NewSource(0))
list := make([]int, size)
for i := range list {
list[i] = i
}
r.Shuffle(len(list), func(i, j int) {
list[i], list[j] = list[j], list[i]
})
return list
}
func BenchmarkInsertIterative(b *testing.B) {
for n := 0; n < b.N; n++ {
list := generateData(4096)
tree := new(BST)
for i := range list {
tree.Insert(&BSTNode{Key: list[i]})
}
}
}
func BenchmarkInsertIterative2(b *testing.B) {
for n := 0; n < b.N; n++ {
list := generateData(4096)
tree := new(BST)
for i := range list {
tree.Insert2(&BSTNode{Key: list[i]})
}
}
}
func BenchmarkInsertRecursive(b *testing.B) {
for n := 0; n < b.N; n++ {
list := generateData(4096)
tree := new(BST)
for i := range list {
tree.InsertRec(&BSTNode{Key: list[i]})
}
}
}> go test -bench=BenchmarkInsert -run=none
goos: windows
goarch: amd64
pkg: example.com
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkInsertIterative-8 2076 541820 ns/op
BenchmarkInsertIterative2-8 2152 531405 ns/op
BenchmarkInsertRecursive-8 1842 659766 ns/op
PASS
> go version
go version go1.20.1 windows/amd64Search
search() gets the value in the tree by given a key.
It is not difficult to implement the search() method. At the first, initialize a current node which is the root of the node. Only if the node is non-nil, compare the key of current and the key you want to find. If the key you want to search is smaller than the current key, go to the left child node, otherwise, go to the right child node.
func (b *BST) Search(key int) (n *BSTNode, found bool) {
for current := b.root; current != nil; {
if current.Key == key {
return current, true
} else if key < current.Key {
current = current.left
} else {
current = current.right
}
}
return nil, false
}Inorder Traverse
In this section, I give two methods to implement traversal, recursive and iterative one. The front one is easier than the later one.
We can use inorder traversal to list the nodes in the tree in increasing order. It is the simplest way to implement inorder traverse by recursive.
// Recursively inorder traverse.
func (n *BSTNode) do(do func(*BSTNode)) {
if n != nil {
n.left.do(do)
do(n)
n.right.do(do)
}
}
func (b *BST) Do(do func(*BSTNode)) {
b.root.do(do)
}Moreover, I provide the other version — an iterative way.
// Iteratively inorder traverse.
func (b *Bst) List() []*Node {
// ret is a list records ordered nodes
// that will be returned
ret := []*Node{}
stack := []*Node{}
current := b.root
for len(stack) != 0 || current != nil {
if current != nil {
// push current into stack
stack = append(stack, current)
current = current.left
} else {
// pop stack
current = stack[len(stack)-1]
stack = stack[:len(stack)-1]
ret = append(ret, current)
current = current.right
}
}
return ret
}It is not easy to understand this version. We can think that when the left child is non-null, we can directly visit it and record the path by pushing them to the stack. Until meeting the nil node, we pop the stack, record the value we popped and go to the right child node.
Delete
It is more difficult to delete a node than insert a node. There are 3 cases that would happen.
- If the deleted node has no child.
- If the deleted node has only one left child or only one right child.
- If the deleted node has both left child and right child.
It is easy to implement delete() on case 1 or case 2. Let the pointer that points to the deleted node be super. If the deleted node has left child set super = deleted_node.left , else super = delted_node.right . Note that because case 1 has neither left child nor right child. Because case 1 does not have left child we execute the code super_pointer = deleted_node.right where deleted_node.right is nil. That is to say, case1 and case2 is the same case.
Delete (Mari, 163) who has no children
Delete (Ruby, 154) who has only right child
Delete (Hanayo, 156) who has both left child and right child
- Find the successor. The node that is printed after the node we want to delete if we inorder traverse this binary search tree. In other words, find the smallest node in the right subtree. We can jump to the right child and go as left as possible. (Hanayo)→(Maki)→(Riko)→(You)
- Replace deleted node (Hanayo) with the successor (You)
- The pointer that points to the successor should be changed to point to the successor’s children. In fact, the successor only has right child because if it has left child, then it is not a successor. That is to say, we only need to set “the pointer that points to the successor” to “the successor’s right subtree”.
Test
// go test -v -run TestBST
func TestBST(t *testing.T) {
nodes := []*person{
{"Hanayo", 156}, {"Hanamaru", 152}, {"Maki", 161},
{"Ruby", 154}, {"Riko", 160}, {"Eli", 162}, {"Mari", 163},
{"Chisato", 155}, {"You", 157}, {"Ayumu", 159},
}
// Create a new binary search tree
tree := new(BST)
// Insert node to the tree
for _, n := range nodes {
tree.Insert(NewBSTNode(n.tall, n.name))
}
// print the tree inorder (way I, recursive)
tree.Do(func(node *BSTNode) {
fmt.Printf("(%d, %v)->", node.Key, node.Val)
})
fmt.Println("nil")
// Print the tree inorder (way II, iterative)
for _, node := range tree.List() {
fmt.Printf("(%d, %v)->", node.Key, node.Val)
}
fmt.Println("nil")
// Delete some nodes in tree
tree.Delete(nodes[6].tall)
tree.Delete(nodes[3].tall)
tree.Delete(nodes[0].tall)
for _, node := range tree.List() {
fmt.Printf("(%d, %v)->", node.Key, node.Val)
}
fmt.Println("nil")
// Search by key: 152
if n, exist := tree.Search(152); exist {
fmt.Println(152, n.Val)
}
}Note that you can run the test function by running go test. You can also enable verbose mode by setting the -v flag.
Result:
(152, Hanamaru)->(154, Ruby)->(155, Chisato)->(156, Hanayo)->(157, You)->(159, Ayumu)->(160, Riko)->(161, Maki)->(162, Eli)->(163, Mari)->nil
(152, Hanamaru)->(154, Ruby)->(155, Chisato)->(156, Hanayo)->(157, You)->(159, Ayumu)->(160, Riko)->(161, Maki)->(162, Eli)->(163, Mari)->nil
(152, Hanamaru)->(155, Chisato)->(157, You)->(159, Ayumu)->(160, Riko)->(161, Maki)->(162, Eli)->nil
152 HanamaruFurthermore, we can design a more complex test function to check the correctness of the insertion and deletion operations.
// go test -run TestBSTCorrectness
func TestBSTCorrectness(t *testing.T) {
// generate an int list
data := generateData(1024)
// create an empty binary search tree
tree := new(BST)
// insert data
for i := range data {
tree.Insert(&BSTNode{Key: data[i]})
}
// check the binary search tree is in increasing order
// and the total number of nodes is equal to the length of `data`
i := 0
start := 0
tree.Do(func(b *BSTNode) {
if b.Key >= start {
start = b.Key
} else {
t.Fail()
}
i++
})
if i != len(data) {
t.Fail()
}
// check that we can access all element by tree.Search()
for i := range data {
_, found := tree.Search(data[i])
if !found {
t.Fail()
}
}
// check that we can remove each nodes
k := len(data)
for i := range data {
tree.Delete(data[i])
k--
// check that the tree is in increasing order
// and the total number of nodes is equal properly
if i%32 == 0 {
n := 0
start := 0
tree.Do(func(b *BSTNode) {
if b.Key >= start {
start = b.Key
} else {
t.Fail()
}
n++
})
if n != k {
t.Fail()
}
}
}
}See the full code: https://github.com/ksw2000/Medium/tree/main/implement-a-binary-search-tree-with-go
See the relative articles:
- Implement an AVL Tree with Go: https://ksw2000.medium.com/implement-an-avl-tree-with-go-49e5952389d4
Reference:
