Binary Search Tree

Terms
Path - Path refers to the sequence of nodes along the edges of a tree
Root - The node at the top of the tree is called root.
         . There is ONLY one root per tree
         . There is Only one path from root node to any node.

Parent - Any node ( except the root node) has one edge upward to a node called parent.
Child - The node below a given node connected by its edge downward is called its child node.
Leaf - The node which does not have any child node is called the leaf node.
Subtree - Subtree represents the descendants of a node.
Visiting - Visiting refers to checking the value of a node when control is on the node.
Traversing - Traversing means passing through nodes in a specific order.
Levels - Level of a node represents the generation of a node. If the root node is at level 0, then its next child is at level1,
         its grandchild is at level 2, and so on.
         this is height of a three, from 0.
Keys - Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Search Tree Representation
A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

golang code

Basic Operations
Insert                         - Insert an element in a tree/create a tree
Search     - Searches an element in a tree
Preorder Traversal - Traverses a tree in a pre-order manner.
Inorder Traversal    - Traverses a tree in an in-order manner.
Postorder Traversal - Traverses a tree in a post-order manner.

Insert Operation
The very first insertion creates the tree. Afterwards, whenever an element is to be inserted, first locate its proper location.
Start searching from the root node, the if the data is less than the key value, search for the empty location in the left subtree and insert the data.
Otherwise, search for the empty location in the right subtree and insert the data.

golang code

Search Operation
Whenever an element is to be searched, start searching fromo the root node, then if the data is less than the key value, search for the element in the left
subtree. Otherwise, search for the element in the right subtree. Follow the same algorighm for each node.

golang code

Traverse Operation
Traversal is a process to visit all the nodes of a tree.Because, all nodes are connected via edges we always start from the root node.
That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree:
.In-order Traversal
.Pre-order Traversal
.Post-order Traversal

In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right subtree.
* We should always remember that every node may represent a subtree itself.

If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-order.
The process goes on until all the nodes are visited. The output of inorder traversal of this tree will be:
D -> B -> E -> A -> F -> C -> G

Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B.
B is also traversed pre-order. The process goes on until all the nodes are visited.
The output of pre-order traversal of this tree will be:
A -> B -> D -> E -> C -> F -> G

Post-order Traversal
In this traversal method, the root node is visited last, hense the name.
First we traverse the left subtree, then the right subtree and finally the root node.
We start from A, and following Post-order traversal, we first visit the left subtree B.
B is also traversed post-order. The process goes on until all the nodes are visited.
The output of post-order traversal of this tree will be:
D -> E -> B -> F -> G -> C -> A

Golang:

  1 package binary_search_tree
  2 
  3 import (
  4     "fmt"
  5 )
  6 
  7 type Node struct {
  8     Data       int
  9     LeftChild  *Node
 10     RightChild *Node
 11 }
 12 
 13 type BinarySearchTree struct {
 14     Root *Node
 15 }
 16 
 17 func (bst *BinarySearchTree) Insert(data int) {
 18     tmpNode := &Node{data, nil, nil}
 19 
 20     if bst.Root == nil {
 21         bst.Root = tmpNode // create root node
 22         return
 23     }
 24 
 25     var parent *Node
 26     current := bst.Root
 27 
 28     for true {
 29         parent = current
 30         if data < parent.Data {
 31             current = parent.LeftChild
 32             if current == nil {
 33                 parent.LeftChild = tmpNode
 34                 return
 35             }
 36         } else {
 37             current = parent.RightChild
 38             if current == nil {
 39                 parent.RightChild = tmpNode
 40                 return
 41             }
 42         }
 43     }
 44 }
 45 
 46 func (bst *BinarySearchTree) Search(data int) *Node {
 47     if bst.Root == nil {
 48         fmt.Println("binary search tree is empty.")
 49         return nil
 50     }
 51 
 52     fmt.Printf("Visiting elements %d, path:", data)
 53     current := bst.Root
 54 
 55     for current.Data != data {
 56         if current != nil {
 57             fmt.Printf(" -> %d", current.Data)
 58         }
 59 
 60         if data < current.Data {
 61             current = current.LeftChild
 62         } else {
 63             current = current.RightChild
 64         }
 65 
 66         if current == nil {
 67             fmt.Printf(" >> %d not found
", data)
 68             return nil
 69         }
 70     }
 71 
 72     fmt.Printf(" -> %d found
", data)
 73     return current
 74 }
 75 
 76 func traverseInOrder(root *Node) {
 77     if root == nil {
 78         return
 79     }
 80 
 81     // visit left child
 82     if root.LeftChild != nil {
 83         traverseInOrder(root.LeftChild)
 84     }
 85 
 86     // visit root
 87     fmt.Printf(" %d", root.Data)
 88 
 89     // visit right child
 90     if root.RightChild != nil {
 91         traverseInOrder(root.RightChild)
 92     }
 93 }
 94 
 95 func traversePreOrder(root *Node) {
 96     if root == nil {
 97         return
 98     }
 99 
100     // visit root
101     fmt.Printf(" %d", root.Data)
102 
103     // visit left child
104     if root.LeftChild != nil {
105         traversePreOrder(root.LeftChild)
106     }
107 
108     // visit right child
109     if root.RightChild != nil {
110         traversePreOrder(root.RightChild)
111     }
112 }
113 
114 func traversePostOrder(root *Node) {
115     if root == nil {
116         return
117     }
118 
119     // visit left child
120     if root.LeftChild != nil {
121         traversePostOrder(root.LeftChild)
122     }
123 
124     // visit right child
125     if root.RightChild != nil {
126         traversePostOrder(root.RightChild)
127     }
128 
129     // visit root
130     fmt.Printf(" %d", root.Data)
131 }
132 
133 func (bst *BinarySearchTree) TraverseInOrder() {
134     if bst.Root == nil {
135         fmt.Println("tree is empty.")
136     }
137     fmt.Print("inorder traversal: ")
138     traverseInOrder(bst.Root)
139     fmt.Println("")
140 }
141 
142 func (bst *BinarySearchTree) TraversePreOrder() {
143     if bst.Root == nil {
144         fmt.Println("tree is empty.")
145     }
146     fmt.Print("preorder traversal: ")
147     traversePreOrder(bst.Root)
148     fmt.Println("")
149 }
150 
151 func (bst *BinarySearchTree) TraversePostOrder() {
152     if bst.Root == nil {
153         fmt.Println("tree is empty.")
154     }
155     fmt.Print("postorder traversal: ")
156     traversePostOrder(bst.Root)
157     fmt.Println(" ")
158 }

Test:

package main

import (
    bst "binary_search_tree"
)

func createTree(bst *bst.BinarySearchTree) {
    bst.Insert(27)
    bst.Insert(35)
    bst.Insert(14)
    bst.Insert(19)
    bst.Insert(42)
    bst.Insert(31)
    bst.Insert(10)
    bst.Insert(8)
    bst.Insert(74)
    bst.Insert(40)
    bst.Insert(23)
    bst.Insert(18)
}

func search(bst *bst.BinarySearchTree) {
    bst.Search(31)
    bst.Search(19)
    bst.Search(42)
    bst.Search(10)
    bst.Search(16)
    bst.Search(8)
    bst.Search(74)
    bst.Search(23)
    bst.Search(71)
}

func traverse(bst *bst.BinarySearchTree) {
    bst.TraverseInOrder()
    bst.TraversePreOrder()
    bst.TraversePostOrder()
}


func main() {
    bst := &bst.BinarySearchTree{}

    //           27
    //        /      
    //      14        35
    //     /        /  
    //   10   19   31    42
    //  /     /         / 
    // 8     18 23     40   74
    createTree(bst)
    search(bst)
    traverse(bst)
}

output:

Visiting elements 31, path: -> 27 -> 35 -> 31 found
Visiting elements 19, path: -> 27 -> 14 -> 19 found
Visiting elements 42, path: -> 27 -> 35 -> 42 found
Visiting elements 10, path: -> 27 -> 14 -> 10 found
Visiting elements 16, path: -> 27 -> 14 -> 19 -> 18 >> 16 not found
Visiting elements 8, path: -> 27 -> 14 -> 10 -> 8 found
Visiting elements 74, path: -> 27 -> 35 -> 42 -> 74 found
Visiting elements 23, path: -> 27 -> 14 -> 19 -> 23 found
Visiting elements 71, path: -> 27 -> 35 -> 42 -> 74 >> 71 not found
inorder traversal:  8 10 14 18 19 23 27 31 35 40 42 74
preorder traversal:  27 14 10 8 19 18 23 35 31 42 40 74
postorder traversal:  8 10 18 23 19 14 31 40 74 42 35 27