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.