👋 Welcome Gophers! In this lesson, we are going to be implementing a Binary Search Tree in Go.
Implementation
Let’s start off by creating a new file called main.go within a new directory called 09-bst/. We’ll build a complete BST implementation from scratch.
First, let’s define our Node struct:
package main
import "fmt"
// Node represents a single node in the Binary Search Tree
type Node struct {
value int
left *Node
right *Node
}
// NewNode creates a new node with a given value
func NewNode(value int) *Node {
return &Node{value: value}
}
Now let’s define our BST struct with the essential methods:
// BST represents a Binary Search Tree
type BST struct {
root *Node
}
// NewBST creates a new empty Binary Search Tree
func NewBST() *BST {
return &BST{}
}
// Insert adds a new value to the BST
func (b *BST) Insert(value int) {
if b.root == nil {
b.root = NewNode(value)
} else {
b.insertNode(b.root, value)
}
}
// insertNode is a helper function that recursively inserts a value
func (b *BST) insertNode(node *Node, value int) {
if value < node.value {
// Go left
if node.left == nil {
node.left = NewNode(value)
} else {
b.insertNode(node.left, value)
}
} else {
// Go right
if node.right == nil {
node.right = NewNode(value)
} else {
b.insertNode(node.right, value)
}
}
}
// Search looks for a value in the BST
// Returns true if found, false otherwise
func (b *BST) Search(value int) bool {
return b.searchNode(b.root, value)
}
// searchNode is a helper function that recursively searches for a value
func (b *BST) searchNode(node *Node, value int) bool {
// Base case: node is nil
if node == nil {
return false
}
fmt.Printf("Checking node with value %d\n", node.value)
if value == node.value {
return true
} else if value < node.value {
// Search left
return b.searchNode(node.left, value)
} else {
// Search right
return b.searchNode(node.right, value)
}
}
Now let’s create a main function to test our BST:
func main() {
fmt.Println("Binary Search Tree Implementation in Go")
// Create a new BST
bst := NewBST()
// Insert values
values := []int{50, 30, 70, 20, 40, 60, 80}
for _, val := range values {
bst.Insert(val)
fmt.Printf("Inserted %d\n", val)
}
fmt.Println("\nSearching for 35:")
found := bst.Search(35)
fmt.Printf("Result: %v\n", found)
fmt.Println("\nSearching for 40:")
found = bst.Search(40)
fmt.Printf("Result: %v\n", found)
}
Running this will output:
$ go run main.go
Binary Search Tree Implementation in Go
Inserted 50
Inserted 30
Inserted 70
Inserted 20
Inserted 40
Inserted 60
Inserted 80
Searching for 35:
Checking node with value 50
Checking node with value 30
Checking node with value 40
Result: false
Searching for 40:
Checking node with value 50
Checking node with value 30
Checking node with value 40
Result: true
Tree Traversal Methods
Let’s add different ways to traverse the tree:
// InOrder traversal: Left, Node, Right (gives sorted order)
func (b *BST) InOrder() []int {
var result []int
b.inOrderHelper(b.root, &result)
return result
}
func (b *BST) inOrderHelper(node *Node, result *[]int) {
if node == nil {
return
}
b.inOrderHelper(node.left, result)
*result = append(*result, node.value)
b.inOrderHelper(node.right, result)
}
// PreOrder traversal: Node, Left, Right
func (b *BST) PreOrder() []int {
var result []int
b.preOrderHelper(b.root, &result)
return result
}
func (b *BST) preOrderHelper(node *Node, result *[]int) {
if node == nil {
return
}
*result = append(*result, node.value)
b.preOrderHelper(node.left, result)
b.preOrderHelper(node.right, result)
}
// PostOrder traversal: Left, Right, Node
func (b *BST) PostOrder() []int {
var result []int
b.postOrderHelper(b.root, &result)
return result
}
func (b *BST) postOrderHelper(node *Node, result *[]int) {
if node == nil {
return
}
b.postOrderHelper(node.left, result)
b.postOrderHelper(node.right, result)
*result = append(*result, node.value)
}
Test the traversals:
func main() {
bst := NewBST()
values := []int{50, 30, 70, 20, 40, 60, 80}
for _, val := range values {
bst.Insert(val)
}
fmt.Println("In-Order (sorted):", bst.InOrder())
fmt.Println("Pre-Order:", bst.PreOrder())
fmt.Println("Post-Order:", bst.PostOrder())
}
Output:
In-Order (sorted): [20 30 40 50 60 70 80]
Pre-Order: [50 30 20 40 70 60 80]
Post-Order: [20 40 30 60 80 70 50]
Finding Minimum and Maximum
Let’s add utility methods:
// FindMin returns the minimum value in the BST
func (b *BST) FindMin() int {
if b.root == nil {
return -1 // or handle error
}
return b.findMinNode(b.root).value
}
func (b *BST) findMinNode(node *Node) *Node {
for node.left != nil {
node = node.left
}
return node
}
// FindMax returns the maximum value in the BST
func (b *BST) FindMax() int {
if b.root == nil {
return -1 // or handle error
}
return b.findMaxNode(b.root).value
}
func (b *BST) findMaxNode(node *Node) *Node {
for node.right != nil {
node = node.right
}
return node
}
Testing Our Implementation
Here are some basic tests:
func TestBSTSearch(t *testing.T) {
bst := NewBST()
values := []int{50, 30, 70, 20, 40, 60, 80}
for _, val := range values {
bst.Insert(val)
}
// Test finding existing values
for _, val := range values {
if !bst.Search(val) {
t.Errorf("Failed to find %d", val)
}
}
// Test finding non-existing values
if bst.Search(100) {
t.Error("Found non-existing value")
}
if bst.Search(25) {
t.Error("Found non-existing value")
}
}
func TestBSTInOrder(t *testing.T) {
bst := NewBST()
values := []int{50, 30, 70, 20, 40, 60, 80}
for _, val := range values {
bst.Insert(val)
}
inOrder := bst.InOrder()
expected := []int{20, 30, 40, 50, 60, 70, 80}
if len(inOrder) != len(expected) {
t.Errorf("Expected %d elements, got %d", len(expected), len(inOrder))
}
for i, val := range inOrder {
if val != expected[i] {
t.Errorf("At index %d: expected %d, got %d", i, expected[i], val)
}
}
}
func TestBSTMinMax(t *testing.T) {
bst := NewBST()
values := []int{50, 30, 70, 20, 40, 60, 80}
for _, val := range values {
bst.Insert(val)
}
if bst.FindMin() != 20 {
t.Error("FindMin failed")
}
if bst.FindMax() != 80 {
t.Error("FindMax failed")
}
}
Conclusion
Awesome! We now have a working implementation of a Binary Search Tree in Go. We’ve implemented insertion, search, multiple traversal methods, and utility functions for finding minimum and maximum values. BSTs are fundamental data structures that provide efficient searching when balanced, and they naturally maintain sorted order.
Quiz Time
Try your hand at these questions below to validate what we’ve just covered in this lesson: