Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   




GO - BINARY SEARCH TREE CODE




Example :



package main
import "fmt"

var root *Node

type Node struct {

    data int
    left *Node
    right *Node
}

func createNode(data int) *Node {

	var node Node

    node.data = data
    node.left = nil
    node.right = nil
    
    return &node
}

func search(key int) *Node {

    return searchNode(root,key)
}

func searchNode(root *Node, key int) *Node {

    if(root == nil) {
        return nil
    }
    if(root.data == key) {
        return root
            
    } else if(root.data < key) {
        return searchNode(root.right, key)
            
    } else {
        return searchNode(root.left, key)
    }
}

func insert(key int) {
    root = insertNode(root, key)
}

    
func insertNode(root *Node, key int) *Node {
        
    if (root == nil) {
        root = createNode(key)
        return root
    }

    if (key < root.data) {
        root.left = insertNode(root.left, key)
    } else if (key > root.data) {
        root.right = insertNode(root.right, key)
	}
	
    return root
}

func inOrder() {
    inOrderNode(root)
}

    
func inOrderNode(root *Node) {
    if (root != nil) {
        inOrderNode(root.left);
        fmt.Print(root.data, "     ");
        inOrderNode(root.right)
    }
}

func delete(key int) {
    root = deleteNode(root, key)
}

func deleteNode(root *Node, key int) *Node{
        
    if (root == nil) {
        return root
    }    
       
    if (key < root.data) {
        root.left = deleteNode(root.left, key)
    } else if (key > root.data) {
            root.right = deleteNode(root.right, key)
    } else {
            
        if (root.left == nil) {
            return root.right;
        } else if (root.right == nil) {
            return root.left
        }    

        root.data = minValue(root.right)

        root.right = deleteNode(root.right, root.data)
    }

    return root
}

func minValue(root *Node) int {
    min := root.data
    for root.left != nil {
        min = root.left.data
        root = root.left
    }
    return min
}


func main() {
        
	insert(16)
    insert(10)
    insert(25)
    insert(13)
    insert(18)

    fmt.Println("Inorder traversal: ")
    inOrder()

    searchedRes := search(5)

    if (searchedRes == nil) {

        fmt.Printf("\n\nThe number 5 is not present in the BST")
    } else {
        fmt.Printf("\n\n",searchedRes.data," is present in the BST");
    }

    fmt.Printf("\n\nLet us delete the element 10 from the Binary Search Tree \n")
    delete(10)
    fmt.Printf("\nInorder traversal after Deletion : \n")
    inOrder()

    insert(3)

    fmt.Printf("\n\nInorder traversal after insertion of the new element 3 : \n")
    inOrder()
    
    fmt.Println()
}


Output :



  Inorder traversal:
  10 13 16 18 25

  The number 5 is not present in the BST

  Let us delete the element 10 from the Binary Search Tree

  Inorder traversal after Deletion :
  13 16 18 25

  Inorder traversal after insertion of the new element 3 :
  3 13 16 18 25

So, we would be constructing the below Binary Search Tree :

java_Collections

And we have the below methods :

  1. func insert(key int) and func insertNode(root *Node, key int) *Node

    The methods are used to insert a new Node to the Binary Search Tree.

  2. func delete(key int) and func deleteNode(root *Node, key int) *Node

    The methods are used to delete a Node from the Binary Search Tree.

  3. func search(key int) *Node and func searchNode(root *Node, key int) *Node

    The methods are used to search, if an element is present in the Binary Search Tree or not.

Code explanation for Binary Search Tree :


Firstly, we would be constructing the above Binary Search Tree, with the help of insert method..


insert(16)

So, we pass the element 16 to the insert(...) method.


And the below insert(...) method is called.


func insert(key int) {
	root = insertNode(root, key)
}

Initially, the pointer type Node variable root is defined in global scope.


var root *Node

Then we take the key i.e. 16 in this case. And pass the root and key to the insertNode() method.


func insertNode(root *Node, key int) *Node {

	if (root == nil) {
		root = createNode(key)
		return root
	}

	if (key < root.data) {
		root.left = insertNode(root.left, key)
	} else if (key > root.data) {
		root.right = insertNode(root.right, key)
	}

	return root
}

The first line checks if the root is null or not.


if (root == nil) {
	root = createNode(key)
	return root
}

And in this case root is nil. So, we create a new Node type variable with the key i.e. 16.


Then assign it to the Node object root.

java_Collections

And return the Node root.


return root

In the next line we try to insert the element 10 in the Binary Search Tree using the insert(...) method.


insert(10)

And the insert(...) method is called.


func insert(key int) {
	root = insertNode(root, key)
}

Which eventually calls insertNode(...) method.


func insertNode(root *Node, key int) *Node {

	if (root == nil) {
		root = createNode(key)
		return root
	}

	if (key < root.data) {
		root.left = insertNode(root.left, key)
	} else if (key > root.data) {
		root.right = insertNode(root.right, key)
	}

	return root
}

And in the similar way we check,


if (key < root.data) {
	root.left = insertNode(root.left, key)
} else if (key > root.data) {
	root.right = insertNode(root.right, key)
}

If the key i.e. 10 is less than the root element root.data. The first condition matches.


if (key < root.data) {
	root.left = insertNode(root.left, key)

And a recursive call is made to insertNode(...) method.


root.left = insertNode(root.left, key)

So, the method executes and returns the Node that contains 10, setting the value of root.left with this Node that contains 10.

java_Collections

Similarly, all the elements are inserted using the insert(...) method.


insert(25)
insert(13)
insert(18)

And the below Binary Search Tree is formed,

java_Collections

Then we use the inOrder() method to traverse the Binary Search Tree.


inOrder()

Next, we search, if the element 5 is present in the Binary Search Tree using the search(...)method.


searchedRes := search(5)

And the search(...) method with one argument is called.


func search(key int) *Node {

	return searchNode(root,key)
}

And the searchNode(...) method is called with the key element as 5(i.e The element to be searched).


func searchNode(root *Node, key int) *Node {

	if(root == nil) {
		return nil
	}
	if(root.data == key) {
		return root

	} else if(root.data < key) {
		return searchNode(root.right, key)

	} else {
		return searchNode(root.left, key)
	}
}

So, there are a couple of if statements, where the first if statement checks if the root element is nil or not.


if(root == nil) {
	return nil
}

In this case the root element is 16. So, we go to the next if statement that checks if the key element 5 (i.e. The element to be searched), is equal to the root element or not.


if(root.data == key) {
	return root
}

In this case the root element is 16 which is not equal to the element that needs to be searched.


So, the next if statement checks, if the element that needs to be searched(i.e. 5) is greater than the root element(i.e. 16) or not.


else if(root.data < key) {
	return searchNode(root.right, key)
}

In this case 5 is less than 16. So, even this condition is not satisfied.


The logic behind this if statement is to check, if the element to be searched is greater than the root element or not. If the element to be searched, is greater than the root element then it should be on the right side of the tree and we are suppose to search there.


Now, since 5 is less than 16. We come to the final else statement. Which assumes that the element to be searched (i.e. 5) is less than the root element (i.e. 16) and must be on the left hand side.


else {
	return searchNode(root.left, key)
}

Now, in this else statement, a recursive call is made to the searchNode(root.left, key) method. So, the assumption is that the element 5 should be in the Left Sub-Tree.


And the func searchNode(root *Node, key int) *Node method is called again with the root as 10.

java_Collections

The same way all the if statements are executed and finally, the element 5 is not found in the Binary Search Tree.


Next, we try to delete the element 10 from the Binary Search Tree.


delete(10)

Calling the delete(...) method.


Similarly, in this case, delete(...) method with one argument is called,


func delete(key int) {
	root = deleteNode(root, key)
}

And the deleteNode(...) method with two arguments is called.


func deleteNode(root *Node, key int) *Node{

	if (root == nil) {
		return root
	}

	if (key < root.data) {
		root.left = deleteNode(root.left, key)
	} else if (key > root.data) {
		root.right = deleteNode(root.right, key)
	} else {

		if (root.left == nil) {
			return root.right;
		} else if (root.right == nil) {
			return root.left
		}

		root.data = minValue(root.right)

		root.right = deleteNode(root.right, root.data)
	}

	return root
}

So, we are trying to delete the element 10 from the Binary Search Tree. So, the key is 10 that we have passed to the delete(...) method.


The delete(...) method is almost same as the search(...) method.


In the search(...) method, we have located the element to be searched. Even in delete(...) method, we will locate the element first(The code is exactly same as the search(...) method). Then call the minValue(root.right) method


The minValue(...) method will find the inorder-successor. i.e. When we delete the element, we need to find a replacement of it, so that the Binary Search Tree properties should be intact.


Thus, we go to the Right Sub-Tree of the element to be deleted. And as we know the Right Sub-Tree contains all the elements that are greater than the root element. So, we have to find the smallest element from the Right Sub-Tree..


And, as we know the smallest element of the Right Sub-Tree resides on the leftmost leaf.


And that's exactly what we will find in int minValue(Node root) method.


func minValue(root *Node) int {
	min := root.data
	for root.left != nil {
		min = root.left.data
		root = root.left
	}
	return min
}