How to Implement the Binary Search Tree(BST) Data Structure in Golang

A binary search tree (BST) is a data structure whose internal nodes store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

In this tutorial, we will see how to implement the BST using Golang. If you are not familiar with its concepts, please go through the following post before starting this tutorial.

In this post, we will see the following

• TreeNode & Tree
• Insert an Element & Insert a Tree node
• Inorder Traverse / Preorder Traverse / Postorder Traverse
• Min / Max
• Binary Search
• Remove Node

TreeNode & Tree

We first define two structs, one for the TreeNode and one for Tree.

• The TreeNode struct contains the key, value, and pointers to its’ left and right TreeNode.
• The Tree struct contains the root node and a mutex to lock the Tree.

Insert an Element & Insert a Tree node

The method InsertElement takes a key and value then constructs a new tree node, then calls the InsertNode function to insert the node into the Tree.

The function InsertNode is not a Tree method because its’ implementation is not specific to the Tree.

In-order Traverse

The methodInOrderTraverseTree takes a function as an argument and calls the inOrderTraverseTree function with the function as an argument.

The traverse result of the example binary search tree is as follows.

Value 1 -> Value 3 > Value 6 -> Value 8 -> Value 10

Preorder Traverse

The traverse result of the example binary search tree is as follows.

Value 8 -> Value 3 > Value 1-> Value 6-> Value 10

Postorder Traverse

The traverse result of the example binary search tree is as follows.

Value 1 -> Value 6 > Value 3 -> Value 10-> Value 8

Min & Max

The method MinNode/MaxNode is used to find the node whose key (not value) is the minimum/maximum.

Remember that there is no need to traverse the entire Tree to find the minimum/maximum.

Because the property of a BST assures the minimum/maximum is always the leftmost/rightmost node.

Binary Search

The method SearchNode is used to search for a node in the Tree. If it is found, it returns the node. If not, it returns nil.

Remove Node

The method RemoveNodeis used to remove a node from the Tree based on the key.

I hope you enjoyed reading this. If you’d like to support me as a writer, consider becoming a Medium member. You’ll also get unlimited access to every story on Medium.