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