Binary Search Tree Implementation in Golang

1. Introduction

A Binary Search Tree (BST) is a type of Binary Tree where the nodes are arranged based on the following properties:

- The left subtree of a node contains only nodes with values less than the node's value.

- The right subtree of a node contains only nodes with values greater than the node's value.

- The left and right subtrees are also BSTs.

BSTs are particularly useful for searching operations, as they facilitate faster look-ups compared to arrays and linked lists.

2. Implementation Steps

1. Define a Node structure with fields for data, left, and right.

2. Implement methods for insertion (Insert), searching (Search), and in-order traversal (InOrder).

3. Enhance the tree with a method to delete a node (Delete).

3. Implementation in Golang

package main
import (
type Node struct {
	data  int
	left  *Node
	right *Node
// Insert a value into the BST
func (n *Node) Insert(value int) {
	if value <= {
		if n.left == nil {
			n.left = &Node{data: value}
		} else {
	} else {
		if n.right == nil {
			n.right = &Node{data: value}
		} else {
// Search for a value in the BST
func (n *Node) Search(value int) bool {
	if n == nil {
		return false
	if value == {
		return true
	if value < {
		return n.left.Search(value)
	return n.right.Search(value)
// InOrder traversal of the BST
func (n *Node) InOrder() {
	if n != nil {
		fmt.Print(, " ")
func main() {
	root := &Node{data: 50}
	fmt.Print("InOrder Traversal: ")
	fmt.Println("\nSearch for 25:", root.Search(25))
	fmt.Println("Search for 60:", root.Search(60))


InOrder Traversal: 20 30 40 50 60 70 80
Search for 25: false
Search for 60: true


1. The Node struct is the foundation of the BST. It consists of the data, left, and right pointers.

2. The Insert method adds a new value into the BST by recursively finding the correct position.

3. The Search method checks for the presence of a value in the BST. It traverses the tree based on the value it's looking for, making the search operation efficient.

4. The InOrder method provides an in-order traversal of the BST which results in a sorted output of the tree's values.

5. In the main function, after inserting nodes into the tree, we demonstrate an in-order traversal and perform a couple of search operations.

This Binary Search Tree forms the foundation for many advanced operations like balancing and finding predecessors or successors of a node.