Binary Search Trees in Go
Introduction
In this post, we’ll be focussing on how binary search trees can be implemented in Golang and why they’re preferred over linear data structures like arrays or linked lists.
While we are still thinking of why trees over arrays and lists, let’s have a basic overview of the major functionalities we will be implementing in this article
- Node insertion.
- Tree Traversal.
- Get Min.
- Get Max.
What are Trees?
Trees are data structures used to represent a hierarchy. They are usually composed of multiple smaller trees. They represent a collection of nodes connected with edges and each node holds data of some type.
Binary trees are a type of tree that can have a maximum of 2 children nodes.
Note:
A binary tree can have nodes in any order but a binary search tree follows a particular order while arranging its nodes as described in the next section.
Why are they required?
Imagine finding an element in an array, the time complexity of achieving this with a linear structure like an array would be O(n) and n increases as the number of elements to search through increases.
Assume that the data were to be represented in a tree structure, the number of steps required to find the value would be reduced by more than half (logarithmic time complexity O(log N)). This happens because whenever a value is inserted into a binary search tree, the addition of the node(data) happens in an ordered way where the value of the left child is less than the value of the parent and the value of the right node is greater than the value of the parent node.
So, when we search for a value and if it’s less than the root, we can ignore the entire right part of the tree and repeat the search process on the left part of the tree recursively.
Quick Terminology
- Node — Every node contains a left pointer and right pointer pointing to the children of the node and some data associated with the node.
- Leaf node — A node with no children
- Root Node — topmost node of a binary tree.
- Edge — Links 2 nodes together.
Binary Search Tree in Go
The main focus of this article is to implement the binary tree structure in Golang along with a couple of functions to add additional nodes, delete nodes, and so on.
A node (referred to as a treenode) can be represented as a struct in Go:
This node structure stores int values but it can be modified to store other data types as well. The left and right fields in the struct point to other tree nodes.
Inserting a Node into the Tree
This is fairly straightforward, we continuously compare the value of the node to be inserted with the nodes in the binary tree. If the value of the data to be inserted is less than the node being compared to, we can insert the new node as the left node if the left child is nil, else we compare it with the left subtree and repeat the process.
Each of these functions is implemented as receiver functions.
Fetch Min
This fetches the minimum element from the tree. The approach is recursive.
We keep checking the value of the left child until it reaches nil value.
Fetch Max
This fetches the maximum element from the tree. The approach is recursive like min.
We keep checking the value of the right child until it reaches nil value.
Traversal in a Binary Search Tree
For a valid binary search tree, the inorder traversal will always be in ascending order.
Inorder traversal is a way of traversing through the binary tree by where the left child is visited first followed by the parent and then the right child of the node. The code below shows a recursive approach for the traversal.
Conclusion
Binary trees are amazing when it comes to data retrieval because they perform much better than linear search operations.
A valid binary tree would have the value of it’s left child lesser than the root and the value of the right child greater than root.
The complete code with a lot of other functionalities is available on -https://github.com/puneeth8994/binary-tree-go-impl
