Golang Binary Search Tree with Example

In this post, we will learn how to implement the binary search tree data structure in Golang with an example.

A binary search tree is a data structure that allows for the quick lookup, addition, and removal of elements. It stores the keys in a sorted order to enable a faster lookup.

On average, space usage for a binary search tree is of the order O(n), whereas the insert, search, and delete operations are of the order O(log n).

Golang Binary Search Tree with Example

Let's create a file named "binary_search_tree.go" and add the following source code to it: 


package main

// importing fmt package
import (
	"fmt"
	"sync"
)

// TreeNode class
type TreeNode struct {
	key       int
	value     int
	leftNode  *TreeNode
	rightNode *TreeNode
}

// BinarySearchTree class
type BinarySearchTree struct {
	rootNode *TreeNode
	lock     sync.RWMutex
}

// InsertElement method
func (tree *BinarySearchTree) InsertElement(key int, value int) {
	tree.lock.Lock()
	defer tree.lock.Unlock()

	var treeNode *TreeNode
	treeNode = &TreeNode{key, value, nil, nil}
	if tree.rootNode == nil {
		tree.rootNode = treeNode
	} else {
		insertTreeNode(tree.rootNode, treeNode)
	}
}

// insertTreeNode method
func insertTreeNode(rootNode *TreeNode, newTreeNode *TreeNode) {
	if newTreeNode.key < rootNode.key {
		if rootNode.leftNode == nil {
			rootNode.leftNode = newTreeNode
		} else {
			insertTreeNode(rootNode.leftNode, newTreeNode)
		}
	} else {
		if rootNode.rightNode == nil {
			rootNode.rightNode = newTreeNode
		} else {
			insertTreeNode(rootNode.rightNode, newTreeNode)
		}
	}
}

// InOrderTraverseTree method
func (tree *BinarySearchTree) InOrderTraverseTree(function func(int)) {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	inOrderTraverseTree(tree.rootNode, function)
}

//  inOrderTraverseTree method
func inOrderTraverseTree(treeNode *TreeNode, function func(int)) {
	if treeNode != nil {
		inOrderTraverseTree(treeNode.leftNode, function)
		function(treeNode.value)
		inOrderTraverseTree(treeNode.rightNode, function)
	}
}

// PreOrderTraverse method
func (tree *BinarySearchTree) PreOrderTraverseTree(function func(int)) {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	preOrderTraverseTree(tree.rootNode, function)
}

//  preOrderTraverseTree method
func preOrderTraverseTree(treeNode *TreeNode, function func(int)) {
	if treeNode != nil {
		function(treeNode.value)
		preOrderTraverseTree(treeNode.leftNode, function)
		preOrderTraverseTree(treeNode.rightNode, function)
	}
}

// PostOrderTraverseTree method
func (tree *BinarySearchTree) PostOrderTraverseTree(function func(int)) {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	postOrderTraverseTree(tree.rootNode, function)
}

//  postOrderTraverseTree method
func postOrderTraverseTree(treeNode *TreeNode, function func(int)) {
	if treeNode != nil {
		postOrderTraverseTree(treeNode.leftNode, function)
		postOrderTraverseTree(treeNode.rightNode, function)
		function(treeNode.value)
	}
}

// MinNode method
func (tree *BinarySearchTree) MinNode() *int {
	tree.lock.RLock()
	defer tree.lock.RUnlock()

	var treeNode *TreeNode
	treeNode = tree.rootNode
	if treeNode == nil {
		return (*int)(nil)
	}
	for {
		if treeNode.leftNode == nil {
			return &treeNode.value
		}
		treeNode = treeNode.leftNode
	}
}

// MaxNode method
func (tree *BinarySearchTree) MaxNode() *int {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	var treeNode *TreeNode
	treeNode = tree.rootNode
	if treeNode == nil {
		return (*int)(nil)
	}
	for {
		if treeNode.rightNode == nil {
			return &treeNode.value
		}
		treeNode = treeNode.rightNode
	}
}

// SearchNode method
func (tree *BinarySearchTree) SearchNode(key int) bool {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	return searchNode(tree.rootNode, key)
}

//  searchNode method
func searchNode(treeNode *TreeNode, key int) bool {
	if treeNode == nil {
		return false
	}
	if key < treeNode.key {
		return searchNode(treeNode.leftNode, key)
	}
	if key > treeNode.key {
		return searchNode(treeNode.rightNode, key)
	}
	return true
}

// RemoveNode method
func (tree *BinarySearchTree) RemoveNode(key int) {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	removeNode(tree.rootNode, key)
}

//  removeNode method
func removeNode(treeNode *TreeNode, key int) *TreeNode {
	if treeNode == nil {
		return nil
	}
	if key < treeNode.key {
		treeNode.leftNode = removeNode(treeNode.leftNode, key)
		return treeNode
	}
	if key > treeNode.key {
		treeNode.rightNode = removeNode(treeNode.rightNode, key)
		return treeNode
	}

	if treeNode.leftNode == nil && treeNode.rightNode == nil {
		treeNode = nil
		return nil
	}
	if treeNode.leftNode == nil {
		treeNode = treeNode.rightNode
		return treeNode
	}
	if treeNode.rightNode == nil {
		treeNode = treeNode.leftNode
		return treeNode
	}
	var leftmostrightNode *TreeNode
	leftmostrightNode = treeNode.rightNode
	for {

		if leftmostrightNode != nil && leftmostrightNode.leftNode != nil {
			leftmostrightNode = leftmostrightNode.leftNode
		} else {
			break
		}
	}
	treeNode.key, treeNode.value = leftmostrightNode.key, leftmostrightNode.value
	treeNode.rightNode = removeNode(treeNode.rightNode, treeNode.key)
	return treeNode
}

// String method
func (tree *BinarySearchTree) String() {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	fmt.Println("************************************************")
	stringify(tree.rootNode, 0)
	fmt.Println("************************************************")
}

// stringify method
func stringify(treeNode *TreeNode, level int) {
	if treeNode != nil {
		format := ""
		for i := 0; i < level; i++ {
			format += "       "
		}
		format += "***> "
		level++
		stringify(treeNode.leftNode, level)
		fmt.Printf(format+"%d\n", treeNode.key)
		stringify(treeNode.rightNode, level)
	}
}

// print method
func print(tree *BinarySearchTree) {
	if tree != nil {

		fmt.Println(" Value", tree.rootNode.value)
		fmt.Printf("Root Tree Node")
		printTreeNode(tree.rootNode)
	} else {
		fmt.Printf("Nil\n")
	}
}

//printTreeNode method
func printTreeNode(treeNode *TreeNode) {
	if treeNode != nil {
		fmt.Println(" Value", treeNode.value)
		fmt.Printf("TreeNode Left")
		printTreeNode(treeNode.leftNode)
		fmt.Printf("TreeNode Right")
		printTreeNode(treeNode.rightNode)
	} else {
		fmt.Printf("Nil\n")
	}

}

// main method
func main() {
	var tree *BinarySearchTree = &BinarySearchTree{}
	tree.InsertElement(8, 8)
	tree.InsertElement(3, 3)
	tree.InsertElement(10, 10)
	tree.InsertElement(1, 1)
	tree.InsertElement(6, 6)
	tree.String()

}

The main() method creates the binary search tree and inserts the elements 8, 3, 10, 1, and 6 into it. tree is printed by invoking the String method.

Run the following command to execute the binary_search_tree.go file: 

G:\GoLang\examples>go run binary_search_tree.go
************************************************
              ***> 1
       ***> 3
              ***> 6
***> 8
       ***> 10
************************************************


Related Go (Golang) Source Code Examples:

Go Tutorial - Hello World App Go function simple example Go function multiple return values Go anonymous function Go variadic function Go recursive function Go defer function call Go pass parameters by value Go function as a parameter Go custom function types Go filter slice example Go closure function example Go higher-order function Go Example: Constants Go Example: Variables Go Example: Arrays Go Example: Slices Go Example: Maps Go Example: Range Go Example: Pointers Go Example: Values Go Example: Base64 Encoding Go Example: Time Formatting / Parsing Go Variable Examples Go Example: Interface Go - Operator Examples Go - Arithmetic Operators Go - Boolean Operators Go - Comparison Operators Go - Bitwise Operators Go - Read Input From User With Scanf Go - Read Input From User With NewReader Go - Read Input From User With NewScanner How to Get Input From User in Golang Go - for Loop Example Go - If/Else Example Go - Switch/Case Statement Example How to Concatenate Strings in Go How to Convert String to Int in Golang How to Convert String to Array in Golang How to Convert String to Int64 in Golang How to Convert Int to String in Golang Go - Array Example Go - Array Iteration Example Go - Multidimensional Array Example How to Iterate Over Arrays in Go Using Range How to Pass Arrays to Functions in Go How to Copy and Clone Arrays in Go How to Convert Array to Slice in Golang How to Sort Array in Golang How to Implement Custom Sort on Arrays in Go How to Open and Close Files in Go How to Read from a File in Go How to Write to a File in Go How to Check if a File Exists in Go How to Delete a File in Go How to Copy a File in Go How to Move or Rename a File in Go How to Change File Permissions in Go How to Create a Directory in Go How to List Files in a Directory in Go How to Recursively Traverse Directories in Go Go - read file into string Go - read file line by line Go - write to file with File.WriteString Go - write to file with ioutil.WriteFile How to read and write a file in GoLang Go - create directory example How to check if a directory exists in Golang Go - create, rename and delete directory examples Go - Create Slice Example Go - Slice Length and Capacity Example Go - Slice Iteration Example Go - Slice Append Example Go - Slice Copy Example Go - Slice Remove Element Example Go - Slice Sorting Example How to Delete Elements from a Slice in Go How to Sort Slice in Golang Go - Multidimensional Slices Example How to Convert an Array to a Slice in Go How to Reverse a Slice in Go How to Concatenate Multiple Slices in Go How to Check if Slice Is Empty Golang Go - Custom Slice Types Example How to Declare and Initialize a Map in Go How to Add or Update Elements in a Map in Go How to Retrieve Values from a Map in Go How to Check if Key Exists in Map Golang How to Iterate Over a Map in Go How to Sort a Map by Key in Go How to Sort a Map by Value in Go How to Pass a Map to a Function in Go How to Copy a Map in Go How to Create Nested Maps in Go How to Compare Maps in Go How to Convert a Map into a Slice in Go Go - Map Example Go - Map loop example Go - Map check if value exists Go - Map remove element example Go Structs Example Go - anonymous struct example Go - nested structs example Go - struct functions fields example Go - struct constructor example Golang - MySQL Delete Example Golang - MySQL Update Example Golang - MySQL Select Example Golang - MySQL Insert Example How to Convert String to JSON in Golang How to Convert Struct to JSON in Golang How to Convert Map to JSON in Golang How to Convert JSON to Map in Golang How to Convert XML to JSON in Golang Golang Interpolation Search Algorithm Golang Recursion Algorithm Golang Binary Search Algorithm Golang Linear Search Algorithm Golang Quick Sort Algorithm Golang Merge Sort Algorithm Golang Shell Sort Algorithm Golang Insertion Sort Algorithm Golang Selection Sort Algorithm Golang AVL Tree with Example Golang Binary Search Tree with Example Design Patterns in Go (Golang) Data Structures and Algorithms in Go

Comments

Post a Comment