In this article, you’ll learn how to implement a custom binary search tree data structure in Go with search and insert operations.
Trees are non-linear abstract data types consisting of nodes connected by edges. It is popular for people to use trees for hierarchical data and cases where the relationship between data is essential.
Binary Search Trees (BSTs) are binary trees (two child nodes per node) optimized for search. In every binary search tree, the left child node holds data less than the parent node’s value, and the right child nodes hold values greater than the parent node’s value.
Binary Search Trees (a.k.a sorted search trees) offer efficient insertion, deletion, and search operations without compromising speed, hence their popularity.
The Go Authors implemented a binary search tree in the sort package. You can check out the source file for the implementation and import the package for your use.
Implementing a Custom Binary Search Tree in Go
You’ll need a struct for your binary search tree. The struct would represent the Nodes in the binary search tree.
type Node struct {
left *Node
right *Node
data int
}
The Node struct represents every node(child or root) in the tree. The leftNode field of type *Node is the reference to the left child of a Node, and the rightNode field is the reference to the right child of a Node. The data variable would hold the value of the node.
The Insertion Algorithm
Implementing the insertion algorithm requires keeping the structure of a binary search tree in mind. If the value you want to insert is less than the parent node’s value, you should insert it on the left child node. The opposite is for the right child node.
func (node *Node) newNode(value int) {
// if the value is less than the Node
if value < node.data {
// if left is nil go to the left
if node.leftNode == nil {
node.leftNode = &Node{
leftNode: nil,
rightNode: nil,
data: value,
}
// if left isn't nil - recursion here
} else {
node.leftNode.newNode(value)
}
// if the value is greater than the Node, Go right
} else {
// if right is nil go to the left
if node.rightNode == nil {
node.rightNode = &Node{
leftNode: nil,
rightNode: nil,
data: value,
}
} else {
// if right isn't nil - recursion here
node.rightNode.newNode(value)
}
}
}
The newNode method implements the Node struct. The first if-statement checks if the value is less than the data in the parent node. If the value is less and the left node is empty, a new node is created, and the value is passed in as the data. After this, the node is inserted.
If the left node isn’t empty, the process is repeated (recursion) until there’s an empty left node and the node satisfies the condition.
The second else-statement negates the first if-statement. The process is the same as the if statement, except that the condition is for the right node, and the data has to be greater than the value of the parent node.
Printing the Binary Search Tree (Traversal)
You’ll need to traverse through the tree to print out the elements in the tree from left to right (sorted).
The printTree method prints the elements in the tree with a comma (,) as the delimiter.
func (node *Node) printTree() {
// prints left
if node.leftNode != nil {
node.leftNode.printTree()
}
// prints a "," as the delimiter
fmt.Print(node.data, ", ")
// prints right
if node.rightNode != nil {
node.rightNode.printTree()
}
}
The printTree method traverse through nodes recursively and print’s the left and right child nodes until it gets to a leaf node (nodes without child nodes).
Searching The Binary Search Tree
A search operation is similar to a print operation; you’ll also have to traverse through the binary search tree. It’s easier to search a tree since you can move in definite directions depending on the magnitude of the value.
func (node *Node) findNode(value int) bool {
if node == nil {
return false
}
if node.data < value {
return node.rightNode.findNode(value)
} else {
return node.leftNode.findNode(value)
}
return true
}
The findNode method takes in the value you’re searching for and returns a bool depending on the search’s outcome. The findNode method traverses through the nodes of the tree. If there’s no match after traversing through the tree, the method evaluates to false, and if the node’s data equals the value, the return true statement is executed.
Interacting With The Binary Search Tree
In this case, you’ll have to instantiate a reference to the struct to interact with the binary search tree.
func main() {
tree := &Node{data: 9}
tree.newNode(2)
tree.newNode(3)
tree.newNode(4)
tree.printTree()
fmt.Println(tree.findNode(7))
}
In the main function, the tree variable is the initialized reference of the binary search tree. Three values are inserted into the tree, and the tree is printed along with Searching for 7. Here’s the output.
Conclusion
This tutorial taught you how to implement a binary search tree in Go with the search, insert and print functionalities.
Binary search trees are one of the most popular and fundamental data structures. This is a result of their ease of implementation, use, and versatility.
