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