How to Implement Binary Search Tree in Go: Simple Guide

To implement a binary search tree in Go, define a Node struct with integer data and pointers to left and right child nodes. Then create functions to insert values and traverse the tree, maintaining the binary search tree property where left child nodes are smaller and right child nodes are larger than the parent.

Syntax

The basic structure of a binary search tree node in Go includes a data field and pointers to left and right child nodes. Functions typically include Insert to add new values and InOrderTraversal to visit nodes in sorted order.

go

type Node struct {
    Data  int
    Left  *Node
    Right *Node
}

func (n *Node) Insert(value int) {
    if n == nil {
        return
    } else if value <= n.Data {
        if n.Left == nil {
            n.Left = &Node{Data: value}
        } else {
            n.Left.Insert(value)
        }
    } else {
        if n.Right == nil {
            n.Right = &Node{Data: value}
        } else {
            n.Right.Insert(value)
        }
    }
}

func (n *Node) InOrderTraversal() {
    if n == nil {
        return
    }
    n.Left.InOrderTraversal()
    fmt.Print(n.Data, " ")
    n.Right.InOrderTraversal()
}

Example

This example shows how to create a binary search tree, insert values, and print them in sorted order using in-order traversal.

go

package main

import "fmt"

type Node struct {
    Data  int
    Left  *Node
    Right *Node
}

func (n *Node) Insert(value int) {
    if n == nil {
        return
    } else if value <= n.Data {
        if n.Left == nil {
            n.Left = &Node{Data: value}
        } else {
            n.Left.Insert(value)
        }
    } else {
        if n.Right == nil {
            n.Right = &Node{Data: value}
        } else {
            n.Right.Insert(value)
        }
    }
}

func (n *Node) InOrderTraversal() {
    if n == nil {
        return
    }
    n.Left.InOrderTraversal()
    fmt.Print(n.Data, " ")
    n.Right.InOrderTraversal()
}

func main() {
    root := &Node{Data: 10}
    root.Insert(5)
    root.Insert(15)
    root.Insert(3)
    root.Insert(7)
    root.Insert(12)
    root.Insert(18)

    fmt.Print("In-order traversal: ")
    root.InOrderTraversal()
    fmt.Println()
}

Output

In-order traversal: 3 5 7 10 12 15 18 

Common Pitfalls

• Not handling the case when the root node is nil before inserting.
• Inserting duplicate values without a clear rule can cause unexpected tree structure.
• Forgetting to use pointers for child nodes leads to copies, not actual tree links.
• Not using recursion or loops properly can cause infinite loops or missed nodes.

go

/* Wrong: Inserting without checking for nil root */
var root *Node
// root.Insert(10) // This will panic because root is nil

/* Right: Initialize root before inserting */
root = &Node{Data: 10}
root.Insert(5)

Quick Reference

• Node struct: Holds data and pointers to left and right children.
• Insert method: Recursively places new values in correct position.
• Traversal: In-order traversal prints values sorted.
• Pointers: Use pointers to link nodes properly.

Key Takeaways

Define a Node struct with data and left/right pointers to build the tree.

Use recursive Insert method to maintain binary search tree order.

Always initialize the root node before inserting values.

Use in-order traversal to visit nodes in sorted order.

Avoid nil pointer errors by checking node existence before operations.