How to Implement a Binary Search Tree in Go

Stdlib
2026-04-17T12:05:42+00:00
Implement a Binary Search Tree in Go using a recursive node struct with insert and search methods.

When a slice gets too slow

You are building a log analyzer that tracks unique error codes. A slice works fine for the first hundred entries. You append codes and search linearly. Then the logs grow. Inserting into a sorted slice requires shifting elements. Searching takes longer. You need a structure that keeps data sorted and allows fast lookups without moving memory around. You reach for a Binary Search Tree.

A Binary Search Tree (BST) organizes data hierarchically. Each node holds a value and pointers to a left child and a right child. The invariant is strict: every value in the left subtree is smaller than the node, and every value in the right subtree is larger. This structure lets you find, insert, and delete values by making a series of binary decisions. Is the target smaller? Go left. Larger? Go right.

The node and the pointers

Go represents a tree using a struct with pointer fields. Pointers are essential here because nodes reference other nodes, and the tree grows dynamically on the heap. A value type cannot contain itself by value, so pointers break the cycle and allow arbitrary depth.

// Node represents a single element in the binary search tree.
// Value holds the data, while Left and Right point to child nodes.
type Node struct {
    Value int
    Left  *Node
    Right *Node
}

The Node struct is exported because it starts with a capital letter. In Go, capitalization controls visibility. If you only need the tree inside a package, lowercase node keeps it private. The convention is to expose the public API and hide internal details. A wrapper type often hides the root pointer so users cannot accidentally corrupt the structure.

Inserting with recursion

Insertion follows the BST invariant. You compare the new value with the current node. If the value is smaller, you recurse into the left child. If larger, you recurse right. When you hit a nil pointer, you have found the insertion point. You create a new node and return it. The return value is critical: each recursive call must update the parent's pointer to link the new node into the tree.

// Insert adds a value to the subtree rooted at this node.
// It returns the root of the modified subtree, preserving the BST invariant.
func (n *Node) Insert(value int) *Node {
    // Base case: nil receiver means we reached an empty spot.
    // Return a new node to anchor the value here.
    if n == nil {
        return &Node{Value: value}
    }

    // Recurse left if the new value is smaller than the current node.
    // Assign the result back to Left to maintain the link.
    if value < n.Value {
        n.Left = n.Left.Insert(value)
    } else {
        // Recurse right for values greater than or equal to the current node.
        // This policy allows duplicates by placing them in the right subtree.
        n.Right = n.Right.Insert(value)
    }

    // Return the current node so the parent can update its pointer.
    // The tree structure remains rooted at n after insertion.
    return n
}

The receiver n is a pointer. Go allows calling methods on a nil pointer, provided the method handles the nil case. This is a powerful idiom. You can call Insert on a nil root without a special check in the caller. The method checks n == nil internally and returns a new node. The caller assigns the result back to the root variable.

var root *Node
root = root.Insert(10)
root = root.Insert(5)
root = root.Insert(15)

If you forget to capture the return value, the tree does not update. root.Insert(10) does nothing if you do not assign the result. The compiler will not stop you, but the logic breaks. The method returns the new root, and you must use it.

Searching the tree

Search is simpler than insertion. You compare the target with the current node. If they match, you return true. If the target is smaller, you search the left subtree. If larger, you search the right. If you reach a nil node, the value is not present.

// Search reports whether the tree contains the target value.
// It returns false if the receiver is nil or the value is not found.
func (n *Node) Search(value int) bool {
    // Nil receiver indicates we exhausted the path without finding the value.
    if n == nil {
        return false
    }

    // Exact match found.
    if value == n.Value {
        return true
    }

    // Target is smaller; continue searching the left subtree.
    if value < n.Value {
        return n.Left.Search(value)
    }

    // Target is larger; continue searching the right subtree.
    return n.Right.Search(value)
}

The compiler enforces type safety. If you pass a string to Search, the build fails with cannot use "hello" (untyped string constant) as int value in argument to Search. Go's static typing catches mismatches early.

Traversal and iteration

A BST is useful for ordered iteration. An in-order traversal visits the left subtree, then the node, then the right subtree. This produces values in sorted order. Recursion makes the implementation concise. You pass a slice to collect results, and each recursive call appends to it.

// InOrder traverses the tree and appends values to the result slice.
// It visits nodes in ascending order: left, current, right.
func (n *Node) InOrder(result []int) []int {
    // Base case: nil node contributes nothing.
    if n == nil {
        return result
    }

    // Visit the left subtree first.
    result = n.Left.InOrder(result)

    // Append the current node's value.
    // append may return a new slice header; capture it to preserve growth.
    result = append(result, n.Value)

    // Visit the right subtree last.
    return n.Right.InOrder(result)
}

Recursion is elegant but carries a risk. Go does not perform tail-call optimization. Deep trees can exhaust the stack. The stack grows dynamically, but a pathological tree with millions of nodes can still trigger a stack overflow. For production code with untrusted input, consider an iterative traversal using an explicit stack.

Generics and type parameters

Go 1.18 introduced generics. You can make the tree work with any type that supports comparison. The constraints.Ordered interface from golang.org/x/exp/constraints restricts the type parameter to integers, floats, and strings. This allows the same tree code to handle different data types.

import "golang.org/x/exp/constraints"

// Node[T] is a generic binary search tree node.
// The type parameter T must be ordered to support comparison operators.
type Node[T constraints.Ordered] struct {
    Value T
    Left  *Node[T]
    Right *Node[T]
}

// Insert adds a value to the generic tree.
// The logic is identical to the int version but works for any ordered type.
func (n *Node[T]) Insert(value T) *Node[T] {
    if n == nil {
        return &Node[T]{Value: value}
    }
    if value < n.Value {
        n.Left = n.Left.Insert(value)
    } else {
        n.Right = n.Right.Insert(value)
    }
    return n
}

Generics add flexibility without runtime overhead. The compiler generates specialized code for each type used. You get type safety and code reuse. Use generics when the algorithm is type-agnostic. Keep concrete types when the logic depends on specific properties.

Pitfalls and runtime errors

Binary Search Trees have several common pitfalls. Unbalanced trees degrade performance. If you insert sorted data into a plain BST, the tree becomes a linked list. Lookups and inserts drop from O(log n) to O(n). Balanced trees like AVL or Red-Black trees prevent this by rotating nodes to maintain height balance. Implementing rotations is complex. Use a balanced tree when worst-case performance matters.

Nil pointer dereferences are a runtime risk. Accessing n.Value when n is nil triggers a panic with runtime error: invalid memory address or nil pointer dereference. Always check for nil before accessing fields. The nil receiver idiom helps, but you must still guard against nil in traversal and deletion logic.

Memory management is handled by the garbage collector, but references matter. If you hold a pointer to a node, the collector cannot reclaim it. Removing a node from the tree requires updating parent pointers and breaking references. Failure to do so causes memory leaks. The collector will not free nodes that are still reachable.

Duplicates require a policy. The example places duplicates in the right subtree. This allows duplicates but can skew the tree. Decide whether duplicates are allowed. If not, ignore the insert or return an error. Consistency is key.

Decision matrix

Use a Binary Search Tree when you need ordered data with frequent insertions and deletions, and you can tolerate O(log n) average performance.

Use a slice with sort.Search when the data is static or rarely changes, as a sorted slice uses less memory and has better cache locality.

Use a map when you only need O(1) lookups and do not care about order, since maps are faster for random access but provide no sorted traversal.

Use a balanced tree like AVL or Red-Black when you must guarantee O(log n) worst-case performance, as a plain BST can degrade to O(n) with sorted input.

Use a heap when you only need access to the minimum or maximum element, as heaps optimize for extremum extraction rather than general search.

Where to go next

Trust the invariant. Check for nil. Balance when it counts.