Golang – Create Binary Search Tree(BST)

# Golang – Create Binary Search Tree(BST)

Binary Search Tree(BST) is a binary tree, where the value of left child is less than value of parent and value of right child is greater than value of parent. In BST, Operations like insert, update,search have running time complexity is O(log(n)) and worst case time complexity is O(n) where n is number of elements. BST is generally used in searching algorithm. In this tutorial we will be creating Binary Search Tree

#### Example of Binary Search Tree

Given data :  10, 25, 2, 1, 14, 30, 5, 7

#### Data structure to store Node of a Binary Search Tree

```type Node struct {
val   int
left  *Node
right *Node
}```

There are two ways to create Binary Search Tree.

1) Recursive
2) Iterative

#### Recursive program to create Binary Search Tree

```package main

import "fmt"

type Node struct {
val   int
left  *Node
right *Node
}

func Insert(root *Node, val int) *Node {
if root == nil {
root = &Node{val, nil, nil}
} else if val > root.val {
root.right = Insert(root.right, val)
} else {
root.left = Insert(root.left, val)
}

return root
}

func Preorder(root *Node) {
if root != nil {
fmt.Printf("%d ", root.val)
Preorder(root.left)
Preorder(root.right)
}
}

func main() {

//10, 25, 2, 1, 14, 30, 5, 7
/*
10
/  \
2	    25
/ \     / \
1   5   14  30
\
7
*/
root := Insert(nil, 10)
Insert(root, 25)
Insert(root, 2)
Insert(root, 1)
Insert(root, 14)
Insert(root, 30)
Insert(root, 5)
Insert(root, 7)

fmt.Println("Preorder traversal")
Preorder(root)
}
```

#### Output

```Preorder traversal
10 2 1 5 7 25 14 30```

#### Iterative program to create Binary Search Tree

```package main

import "fmt"

type Node struct {
val   int
left  *Node
right *Node
}

func InsertIterative(root *Node, val int) *Node {
current := root
previous := root

if root == nil {
root = &Node{val, nil, nil}
return root
}

for current != nil {
previous = current
if val < current.val {
current = current.left
} else {
current = current.right
}
}

if val < previous.val {
previous.left = &Node{val, nil, nil}
} else {
previous.right = &Node{val, nil, nil}
}

return root
}

func Preorder(root *Node) {
if root != nil {
fmt.Printf("%d ", root.val)
Preorder(root.left)
Preorder(root.right)
}
}

func main() {

//10, 25, 2, 1, 14, 30, 5, 7
/*
10
/  \
2	    25
/ \     / \
1   5   14  30
\
7
*/
root := InsertIterative(nil, 10)
InsertIterative(root, 25)
InsertIterative(root, 2)
InsertIterative(root, 1)
InsertIterative(root, 14)
InsertIterative(root, 30)
InsertIterative(root, 5)
InsertIterative(root, 7)

fmt.Println("Preorder traversal")
Preorder(root)
}
```

#### Output

```Preorder traversal
10 2 1 5 7 25 14 30```