Golang Binary Search Tree

A Tree is a non-linear Data Structure unlike the arrays, slices, and linked lists. A Binary Tree is also a tree and data structure that has a maximum of two children nodes.

The Binary Search Tree allows us for a quick lookup, insertion, and deletion of nodes/elements. The time complexity of these operations in Binary Search Tree is O(log n).

Binary Search Tree was invented by P. F Windley, A.D. Booth, A. J. T. Colin, and T. N. Hibbard.

Prerequisite for the Binary Search Tree is you should know about Golang pointers and a little knowledge about Golang linked list.

Binary Search Tree Node Struct in Golang

The BST consists of nodes with these properties:

The Left field of type node that stores the address of the root of the left subtree.
Data field to store data.
The right field of type node to store the address of the root of the right subtree.

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

Golang Binary Search Tree Struct

The Binary Search Tree Struct has a root field that stores the value of the root of the tree.

The root of the tree holds a very significant place because we need the root of the tree to traverse the tree.

type BinarySearchTree struct {
    root *Node
}

Read the whole post on Golang Binary Search Tree from the original Post.