Binary Search Tree in Golang

In the previous blog about Golang Data Structures, we learned about Linked lists. This blog will guide about the representation and implementation of Binary Search Tree in Golang.

A Tree is a non-linear Data Structure unlike the arrays, slices, and linked lists. A Binary Tree is also a tree and data structure that has a maximum of two children nodes.

The Binary Search Tree allows us for a quick lookup, insertion, and deletion of nodes/elements. The time complexity of these operations in Binary Search Tree is O(log n).

Binary Search Tree was invented by P. F Windley, A.D. Booth, A. J. T. Colin, and T. N. Hibbard.

Prerequisite for the Binary Search Tree is you should know about Golang pointers and a little knowledge about Golang linked list.

BST Node Struct

The BST consists of nodes with these properties:

• The Left field of type node that stores the address of the root of the left subtree.
• Data field to store data.
• The right field of type node to store the address of the root of the right subtree.

type Node struct {
	left *Node
	data int
	right *Node
}

Golang Binary Search Tree Struct

The Binary Search Tree Struct has a root field that stores the value of the root of the tree.

The root of the tree holds a very significant place because we need the root of the tree to traverse the tree.

type BinarySearchTree struct {
	root *Node
}

Binary Search Tree Insert Method

The insert method that is associated with the BinarySearchTree Struct checks if the root of the tree is nil or not. If the root of the tree is found nil, first of all, the root of the tree is created.

If the root of the tree is not nil, the insert method associated with the Node Struct is called that compares the data value from its parent node and then decides where to put the node.

The node is put to the left of the parent node if the data is smaller than the parent node else to the right. This is the core behavior of the Binary Search Tree.

// Method associated to BinarySearchTree struct
func (tree *BinarySearchTree) insert(data int) *BinarySearchTree {
	if tree.root == nil {
		tree.root = &Node{data: data, left: nil, right: nil}
	} else {
		tree.root.insert(data)
	}
	return tree
}
// Method associated to Node struct
func (node *Node) insert(data int) {
	if node == nil {
		return
	} else if data < node.data {
		if node.left == nil {
			node.left = &Node{data: data, left: nil, right: nil}
		} else {
			node.left.insert(data)
		}
	} else {
		if node.right == nil {
			node.right = &Node{data: data, left: nil, right: nil}
		} else {
			node.right.insert(data)
		}
	}
}

Inserting Data to the Tree

Data is inserted into the tree in the main function of the Golang.

func main() {
	tree := &BinarySearchTree{}
	tree.insert(10)
	tree.insert(5)
	tree.insert(15)
	tree.insert(4)
	tree.insert(16)
	tree.insert(6)
	tree.insert(13)
	tree.insert(1)
	tree.insert(12)
	tree.insert(2)
	tree.insert(20)
	inOrder(tree.root)
}

Golang InOrder Tree Traversal

Inorder traversal of a binary search tree gives a sorted list of data. This is a great moment to check the tree data structure that we created is correct or not.

// InOrder Traversal
func inOrder(root *Node) {
	if root == nil {
		return
	}
	inOrder(root.left)
	fmt.Print(root.data, " ")
	inOrder(root.right)
}

Output:

1 2 4 5 6 10 12 13 15 16 20

This states that the tree Data Structure in Golang is correct.

Learn more about Golang from the official website Golang.org