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

```
```

1. 2. 3. 