Binary Search tree implementation (BST) using Golang

 Binary Search tree(BST): In today post we are going to see implementation of bst using Go, bst is widely asked in most of interview for each tech companies. Its most used data structure and  its starting points for learning data structure where we can store the our data in sorted form, its easy to search and used in most of application.

Definition From Wikipedia: a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

In above picture you can see that, data storage in sorted order when small number goes to left side and number which greater than root is go on right side.

Below is the application where we used BST, its informative because most of time interviewer or people asked where we use BST, Please refer below image which i search over internet.

In above image you can see there are multiple application which use bst in different ways.

Implementation using Go:

First we need to define the our bst node structure like how we going to store data:

type bst struct {
    nodeValue int
    leftNode  *bst
    rightNode *bst
}

In above code you can see that we create a node which have  nodeValue means that where we going to store our value, with two left and right child where we going to store its subtree.

Full Code:

 

package main

import "fmt"

type bst struct {
	rootValue int
	leftNode  *bst
	rightNode *bst
}

//createNode used to create a node for binary search tree
func createNode(value int) *bst {
	return &bst{
		rootValue: value,
		leftNode:  nil,
		rightNode: nil,
	}
}

func (root *bst) Insert(value int) {
	if value < root.rootValue {
		if root.leftNode == nil {
			root.leftNode = createNode(value)
			return
		}
		root.leftNode.Insert(value)
	}
	if value > root.rootValue {
		if nil == root.rightNode {
			root.rightNode = createNode(value)
			return
		}
		root.rightNode.Insert(value)
	}
	//if its going to equal to root value
	//then we are going to ignore that value
	//we don't want duplicate value
}

//InOrder print node of tree
func (root *bst) InOrder() {
	if nil == root {
		return
	}
	root.leftNode.InOrder()
	fmt.Printf("%d ", root.rootValue)
	root.rightNode.InOrder()
}

func main() {
	numbers := []int{5, 10, 1, 21, 11, 7, 9}
	var root *bst
	var rootNode bool = true
	for _, value := range numbers {
		if rootNode {
			root = createNode(value)
			rootNode = false
		}
		root.Insert(value)
	}
	//lets print the tree
	root.InOrder()
	fmt.Println()
}


 

 

Run Code:

go run bst.go

output: 1 5 7 9 10 11 21

Full code for binary search tree where we implemeted is as method calling way, For printing the   tree in sorted order. That is one of property of binary search tree like whenever we print a binary search tree using inorder its print in sorting order. Most of company like Microsoft, google, amazon, cloud related companies asked mostly question on BST. 

In future post i am going to post about preorder traversal, postorder traversal and try to solve as many as question as possible using golang which mostly asked in tech interview. 

There are not any Golang binary search tree library official but soon when go start support generic we can see that.

If you interested in Binary search tree golang github code, you can check this link.

Let me know in comment if anything wrong or you have any question.