Deletion in binary Search tree examples(BST) using Golang

We'll learn how to remove a node from a binary search tree using Go in this post. As we already know, in a binary search tree, all tiny nodes are on the left side of the root node, while those with values higher than the root value are on the right side.
For the delete operation, we must first locate an existing node based on the supplied input number, and then remove that node using one of the traversal methods such as preorder, postorder, or inorder.

After deleting a node from BST, we must ensure that the provided tree follows the bst property, which is the most difficult task.

I solved this problem in Golang by checking all of the corner cases and appropriately deleting the node using proper pointer handling. We first take care of all the leaf nodes, because deleting a single leaf node causes no problems, and deleting a single child node does not require managing the pointer, but in the case of nodes with both child nodes, such as the left child tree and the right child tree, we select the minimum node of the right subtree and replace the data, then delete that minimum value node.
Its implementation is not difficult; we only need to pay close attention to pointers and recursion.

Full Implementation Using Go:

 

package main

import (
	"fmt"
	"time"
)

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()
}

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

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

func (root *bst) LevelWiseTraversal() {
	nodeList := make([]*bst, 0)
	if nil == root {
		return
	}
	temp := &bst{}
	nodeList = append(nodeList, root)
	for len(nodeList) > 0 {
		temp, nodeList = nodeList[0], nodeList[1:]
		if nil != temp.leftNode {
			//enqueue in the list
			nodeList = append(nodeList, temp.leftNode)
		}
		if nil != temp.rightNode {
			nodeList = append(nodeList, temp.rightNode)
		}
		fmt.Printf("%d\t", temp.rootValue)
		time.Sleep(1 * time.Second)
	}
	fmt.Println()
}

func minValued(root *bst) *bst {
	temp := root
	for nil != temp && temp.leftNode != nil {
		temp = temp.leftNode
	}
	return temp
}

//Delete node from binary search tree
func Delete(root *bst, val int) *bst {
	if nil == root {
		return root
	}
	if root.rootValue > val {
		root.leftNode = Delete(root.leftNode, val)
	}
	if root.rootValue < val {
		root.rightNode = Delete(root.rightNode, val)
	}
	if root.rootValue == val {
		if root.leftNode == nil && root.rightNode == nil {
			root = nil
			return root
		}
		if root.leftNode == nil && root.rightNode != nil {
			temp := root.rightNode
			root = nil
			root = temp
			return root
		}
		if root.leftNode != nil && root.rightNode == nil {
			temp := root.leftNode
			root = nil
			root = temp
			return root
		}

		tempNode := minValued(root.rightNode)
		root.rootValue = tempNode.rootValue
		root.rightNode = Delete(root.rightNode, tempNode.rootValue)
	}
	return root
}

func main() {
	numbers := []int{50, 30, 20, 40, 70, 60, 80}
	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()
	//Delete a node
	Delete(root, 20)
	root.InOrder()
	fmt.Println()
}