Golang DSA Chapter 4 Part 1: Trees in Go
Up to this point in the book, everything we covered was linear. Lists, stacks, queues, heaps, all of them store data in a straight line. One element after another. Chapter 4 is where things get interesting because we’re moving into non-linear data structures.
And the first big one? Trees.
What Are Non-Linear Data Structures?
Think of linear structures like a single-lane road. You go forward, you go backward, that’s it. Non-linear structures are more like a city map, where one point can connect to many other points.
A few things that make non-linear structures different:
- An element can connect to multiple other elements
- They use memory efficiently, you don’t need big chunks of contiguous memory
- You can’t just loop through all elements in one simple pass
- They’re harder to implement, but way more powerful for certain problems
The book covers trees, tables, containers, and hash functions in this chapter. This post handles the tree side of things. We’ll get to hash tables in Part 2.
Trees: The Basics
A tree is exactly what it sounds like, if you flip an actual tree upside down. You have a root node at the top, and it branches out into child nodes below. Each child can have its own children, and so on.
A binary tree is a tree where each node has at most two children. That’s the “binary” part, two options, left or right.
A binary search tree (BST) adds one extra rule: for any node, everything in the left subtree has smaller values, and everything in the right subtree has bigger values. This property is what makes searching fast.
Binary Search Tree in Go
The book starts with a full BST implementation. Let’s walk through it.
First, the node structure. Each node holds a key, a value, and pointers to its left and right children:
type TreeNode struct {
key int
value int
leftNode *TreeNode
rightNode *TreeNode
}
Then the tree itself. Notice it uses a sync.RWMutex for thread safety, which is a nice touch if you’re working with concurrent code:
type BinarySearchTree struct {
rootNode *TreeNode
lock sync.RWMutex
}
Inserting Elements
To add an element, you lock the tree, create a new node, then figure out where it belongs. If the tree is empty, the new node becomes the root. Otherwise, you walk down the tree comparing keys:
func (tree *BinarySearchTree) InsertElement(key int, value int) {
tree.lock.Lock()
defer tree.lock.Unlock()
var treeNode *TreeNode
treeNode = &TreeNode{key, value, nil, nil}
if tree.rootNode == nil {
tree.rootNode = treeNode
} else {
insertTreeNode(tree.rootNode, treeNode)
}
}
The actual placement logic is recursive. If the new key is smaller than the current node’s key, go left. If it’s bigger, go right. Keep going until you find an empty spot:
func insertTreeNode(rootNode *TreeNode, newTreeNode *TreeNode) {
if newTreeNode.key < rootNode.key {
if rootNode.leftNode == nil {
rootNode.leftNode = newTreeNode
} else {
insertTreeNode(rootNode.leftNode, newTreeNode)
}
} else {
if rootNode.rightNode == nil {
rootNode.rightNode = newTreeNode
} else {
insertTreeNode(rootNode.rightNode, newTreeNode)
}
}
}
Pretty straightforward. The recursion does the heavy lifting.
Traversing the Tree
There are three classic ways to walk through a binary tree. The book implements all three.
In-order traversal visits: left subtree, current node, right subtree. For a BST, this gives you elements in sorted order, which is really useful:
func inOrderTraverseTree(treeNode *TreeNode, function func(int)) {
if treeNode != nil {
inOrderTraverseTree(treeNode.leftNode, function)
function(treeNode.value)
inOrderTraverseTree(treeNode.rightNode, function)
}
}
Pre-order traversal visits: current node first, then left, then right. Good for making copies of the tree:
func preOrderTraverseTree(treeNode *TreeNode, function func(int)) {
if treeNode != nil {
function(treeNode.value)
preOrderTraverseTree(treeNode.leftNode, function)
preOrderTraverseTree(treeNode.rightNode, function)
}
}
Post-order traversal visits: left, right, then current node. Useful when you need to delete nodes safely or evaluate expressions:
func postOrderTraverseTree(treeNode *TreeNode, function func(int)) {
if treeNode != nil {
postOrderTraverseTree(treeNode.leftNode, function)
postOrderTraverseTree(treeNode.rightNode, function)
function(treeNode.value)
}
}
Notice how all three are basically the same code, just with the function(treeNode.value) call in different positions. That’s the only difference between them. Each traversal method also has a public wrapper that handles the locking.
Finding Min and Max
Because of how a BST is organized, finding the minimum value is simple: just keep going left until you can’t anymore. The maximum? Keep going right:
func (tree *BinarySearchTree) MinNode() *int {
tree.lock.RLock()
defer tree.lock.RUnlock()
var treeNode *TreeNode
treeNode = tree.rootNode
if treeNode == nil {
return (*int)(nil)
}
for {
if treeNode.leftNode == nil {
return &treeNode.value
}
treeNode = treeNode.leftNode
}
}
The MaxNode method is the mirror image, it follows right nodes instead of left ones.
Searching
Searching a BST is like a guessing game. Start at the root. Is the key you want smaller? Go left. Bigger? Go right. Found it? Return true. Hit nil? It’s not in the tree:
func searchNode(treeNode *TreeNode, key int) bool {
if treeNode == nil {
return false
}
if key < treeNode.key {
return searchNode(treeNode.leftNode, key)
}
if key > treeNode.key {
return searchNode(treeNode.rightNode, key)
}
return true
}
This is where the BST property pays off. On average, search is O(log n) because you cut the search space in half at every step.
Removing Nodes
Deletion is the trickiest part. There are three cases to handle:
- Leaf node (no children): just remove it
- One child: replace the node with its child
- Two children: find the smallest node in the right subtree (the “in-order successor”), swap values, then delete that successor
func removeNode(treeNode *TreeNode, key int) *TreeNode {
if treeNode == nil {
return nil
}
if key < treeNode.key {
treeNode.leftNode = removeNode(treeNode.leftNode, key)
return treeNode
}
if key > treeNode.key {
treeNode.rightNode = removeNode(treeNode.rightNode, key)
return treeNode
}
// key == node.key
if treeNode.leftNode == nil && treeNode.rightNode == nil {
treeNode = nil
return nil
}
if treeNode.leftNode == nil {
treeNode = treeNode.rightNode
return treeNode
}
if treeNode.rightNode == nil {
treeNode = treeNode.leftNode
return treeNode
}
var leftmostrightNode *TreeNode
leftmostrightNode = treeNode.rightNode
for {
if leftmostrightNode != nil && leftmostrightNode.leftNode != nil {
leftmostrightNode = leftmostrightNode.leftNode
} else {
break
}
}
treeNode.key, treeNode.value = leftmostrightNode.key, leftmostrightNode.value
treeNode.rightNode = removeNode(treeNode.rightNode, treeNode.key)
return treeNode
}
The two-children case is the interesting one. You find the leftmost node in the right subtree (smallest value that’s still bigger than the current node), copy its key and value over, then recursively delete that leftmost node.
Printing the Tree
The book includes a stringify helper that prints the tree visually with indentation based on depth:
func stringify(treeNode *TreeNode, level int) {
if treeNode != nil {
format := ""
for i := 0; i < level; i++ {
format += " "
}
format += "---[ "
level++
stringify(treeNode.leftNode, level)
fmt.Printf(format+"%d\n", treeNode.key)
stringify(treeNode.rightNode, level)
}
}
Putting It All Together
The main function builds a small tree and prints it:
func main() {
var tree *BinarySearchTree = &BinarySearchTree{}
tree.InsertElement(8, 8)
tree.InsertElement(3, 3)
tree.InsertElement(10, 10)
tree.InsertElement(1, 1)
tree.InsertElement(6, 6)
tree.String()
}
This inserts 8 as the root, then 3 goes left, 10 goes right, 1 goes left of 3, and 6 goes right of 3. The String() method prints the structure so you can visually confirm everything landed in the right spot.
AVL Trees
Regular BSTs have a problem. If you insert elements in sorted order (like 1, 2, 3, 4, 5), you end up with a tree that looks like a linked list. All nodes chain to the right. Search becomes O(n) instead of O(log n). Not great.
AVL trees fix this. Named after Adelson, Velski, and Landis (the folks who invented them), AVL trees are self-balancing binary search trees. After every insert or delete, the tree checks if it’s become lopsided and rotates nodes to fix it.
The balance factor is the difference between the heights of the left and right subtrees. If it goes above 1 or below -1, rotations kick in.
The book defines a KeyValue interface for comparison:
type KeyValue interface {
LessThan(KeyValue) bool
EqualTo(KeyValue) bool
}
And a different TreeNode for the AVL tree that includes a balance value and uses an array of two pointers for its children (index 0 for left, index 1 for right):
type TreeNode struct {
KeyValue KeyValue
BalanceValue int
LinkedNodes [2]*TreeNode
}
Rotations
Rotations are the magic that keeps AVL trees balanced. There are two types.
Single rotation moves one node up and one node down. Think of it like tilting a seesaw:
func singleRotation(rootNode *TreeNode, nodeValue int) *TreeNode {
var saveNode *TreeNode
saveNode = rootNode.LinkedNodes[opposite(nodeValue)]
rootNode.LinkedNodes[opposite(nodeValue)] = saveNode.LinkedNodes[nodeValue]
saveNode.LinkedNodes[nodeValue] = rootNode
return saveNode
}
The opposite helper is just 1 - nodeValue, flipping between 0 and 1 (left and right).
Double rotation is two single rotations combined. It handles the case where a simple single rotation wouldn’t fix the imbalance:
func doubleRotation(rootNode *TreeNode, nodeValue int) *TreeNode {
var saveNode *TreeNode
saveNode = rootNode.LinkedNodes[opposite(nodeValue)].LinkedNodes[nodeValue]
rootNode.LinkedNodes[opposite(nodeValue)].LinkedNodes[nodeValue] =
saveNode.LinkedNodes[opposite(nodeValue)]
saveNode.LinkedNodes[opposite(nodeValue)] =
rootNode.LinkedNodes[opposite(nodeValue)]
rootNode.LinkedNodes[opposite(nodeValue)] = saveNode
saveNode = rootNode.LinkedNodes[opposite(nodeValue)]
rootNode.LinkedNodes[opposite(nodeValue)] = saveNode.LinkedNodes[nodeValue]
saveNode.LinkedNodes[nodeValue] = rootNode
return saveNode
}
Yeah, that’s a lot of pointer shuffling. The gist is: when one side of the tree gets too heavy, you rearrange nodes to spread the weight more evenly. All operations (search, insert, delete) stay at O(log n) because the tree never gets too lopsided.
Quick Performance Recap
| Operation | BST Average | BST Worst | AVL (all cases) |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) |
| Space | O(n) | O(n) | O(n) |
The AVL tree trades a bit of extra work during inserts and deletes (to maintain balance) for guaranteed fast lookups. If your use case involves lots of searches and relatively fewer writes, AVL trees are a solid choice.
What’s Next
That covers the tree foundations from the first half of Chapter 4. We went from basic BST operations (insert, search, delete, traverse) to AVL trees and how they keep themselves balanced with rotations.
In Part 2, we’ll cover the rest of Chapter 4: hash tables, hash functions, and how Go handles all of that.
This post is part of a series retelling “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). You can find the full series in the intro post.