Golang DSA Chapter 7 Part 1: Dictionaries and TreeSets

We’re into Chapter 7 of “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi, and this is where things get interesting. The chapter is about dynamic data structures, which are basically collections that can grow and shrink as needed. No fixed sizes, no guessing how much memory you need upfront.

If you’ve worked with databases or caching systems, a lot of this will feel familiar. Dictionaries, TreeSets, and sequences are the main topics. In this first part, we’ll cover dictionaries and TreeSets. Sequences get their own post in Part 2.

What Are Dynamic Data Structures?

A dynamic data structure is a collection that can expand or shrink at runtime. You don’t have to decide the size ahead of time. This makes them really useful when you’re dealing with data that changes a lot, like adding and removing items from a key-value store, managing customer records, or handling distributed caching.

Think of them as somewhere between a simple array and a full database. They give you the flexibility to add, remove, modify, and look up elements without the overhead of spinning up a database connection.

The book mentions several real-world uses: phone directories, router tables in networking, page tables in operating systems, symbol tables in compilers, and even genome maps in biology. Pretty wide range.

Dictionaries in Go

A dictionary is a collection of unique keys, each mapped to a value. If you’ve used Python dicts, Java HashMaps, or even Go’s built-in map type, you already know the concept. The difference here is that the book builds a dictionary struct from scratch with thread safety built in.

Setting Up the Types

First, we define custom types for keys and values. Both are strings in this example:

// DictKey type
type DictKey string

// DictVal type
type DictVal string

Then the Dictionary struct itself. Notice it uses sync.RWMutex for thread-safe access. This matters when multiple goroutines are reading and writing at the same time:

// Dictionary class
type Dictionary struct {
    elements map[DictKey]DictVal
    lock     sync.RWMutex
}

The Put Method

Adding items to the dictionary. The method grabs a write lock, checks if the internal map has been initialized, creates it if not, then sets the key-value pair:

func (dict *Dictionary) Put(key DictKey, value DictVal) {
    dict.lock.Lock()
    defer dict.lock.Unlock()
    if dict.elements == nil {
        dict.elements = make(map[DictKey]DictVal)
    }
    dict.elements[key] = value
}

The defer dict.lock.Unlock() pattern is classic Go. It guarantees the lock gets released no matter what happens in the rest of the function.

The Remove Method

Removing an element checks if the key exists first, deletes it if found, and returns a boolean to let you know if anything was actually removed:

func (dict *Dictionary) Remove(key DictKey) bool {
    dict.lock.Lock()
    defer dict.lock.Unlock()
    var exists bool
    _, exists = dict.elements[key]
    if exists {
        delete(dict.elements, key)
    }
    return exists
}

The Contains Method

A simple check to see if a key exists. Notice it uses RLock (read lock) instead of Lock (write lock), because we’re only reading:

func (dict *Dictionary) Contains(key DictKey) bool {
    dict.lock.RLock()
    defer dict.lock.RUnlock()
    var exists bool
    _, exists = dict.elements[key]
    return exists
}

This is an important detail. RLock allows multiple goroutines to read at the same time. A full Lock would block everyone else, even other readers. Using the right lock type matters for performance.

The Find Method

Looking up a value by key. Also uses a read lock:

func (dict *Dictionary) Find(key DictKey) DictVal {
    dict.lock.RLock()
    defer dict.lock.RUnlock()
    return dict.elements[key]
}

The Reset Method

Wipes the dictionary clean by creating a fresh empty map:

func (dict *Dictionary) Reset() {
    dict.lock.Lock()
    defer dict.lock.Unlock()
    dict.elements = make(map[DictKey]DictVal)
}

Helper Methods

The dictionary also has a few utility methods. NumberOfElements returns the count:

func (dict *Dictionary) NumberOfElements() int {
    dict.lock.RLock()
    defer dict.lock.RUnlock()
    return len(dict.elements)
}

GetKeys collects all keys into a slice:

func (dict *Dictionary) GetKeys() []DictKey {
    dict.lock.RLock()
    defer dict.lock.RUnlock()
    var dictKeys []DictKey
    dictKeys = []DictKey{}
    var key DictKey
    for key = range dict.elements {
        dictKeys = append(dictKeys, key)
    }
    return dictKeys
}

And GetValues does the same for values:

func (dict *Dictionary) GetValues() []DictVal {
    dict.lock.RLock()
    defer dict.lock.RUnlock()
    var dictValues []DictVal
    dictValues = []DictVal{}
    var key DictKey
    for key = range dict.elements {
        dictValues = append(dictValues, dict.elements[key])
    }
    return dictValues
}

Putting It Together

Here’s how you use the dictionary:

func main() {
    var dict *Dictionary = &Dictionary{}
    dict.Put("1", "1")
    dict.Put("2", "2")
    dict.Put("3", "3")
    dict.Put("4", "4")
    fmt.Println(dict)
}

Run it with go run dictionary.go and you get the dictionary printed out with its key-value pairs. Simple and clean.

TreeSets

A TreeSet is a set backed by a binary search tree. The elements are unique and stored in sorted order. If you need a collection where items are always sorted and you don’t want duplicates, this is your go-to structure.

The book mentions that add, remove, and contains operations on a TreeSet cost O(log n), which is pretty good. Compare that to an unsorted list where searching costs O(n).

The TreeSet Struct

The TreeSet wraps a binary search tree:

type TreeSet struct {
    bst *BinarySearchTree
}

Inserting Nodes

The InsertTreeNode method accepts variadic arguments, so you can insert one node or many at once:

func (treeset *TreeSet) InsertTreeNode(treeNodes ...TreeNode) {
    var treeNode TreeNode
    for _, treeNode = range treeNodes {
        treeset.bst.InsertElement(treeNode.key, treeNode.value)
    }
}

Deleting Nodes

Deletion works the same way, taking variadic tree nodes and removing them by key:

func (treeset *TreeSet) Delete(treeNodes ...TreeNode) {
    var treeNode TreeNode
    for _, treeNode = range treeNodes {
        treeset.bst.RemoveNode(treeNode.key)
    }
}

Traversing the Tree

The book shows two traversal methods. In-order traversal visits left subtree, then root, then right subtree. This gives you elements in sorted order:

func (tree *BinarySearchTree) InOrderTraverseTree(function func(int)) {
    tree.lock.RLock()
    defer tree.lock.RUnlock()
    inOrderTraverseTree(tree.rootNode, function)
}

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 root first, then left, then right. This is useful for copying the tree or getting a prefix representation:

func (tree *BinarySearchTree) PreOrderTraverseTree(function func(int)) {
    tree.lock.Lock()
    defer tree.lock.Unlock()
    preOrderTraverseTree(tree.rootNode, function)
}

func preOrderTraverseTree(treeNode *TreeNode, function func(int)) {
    if treeNode != nil {
        function(treeNode.value)
        preOrderTraverseTree(treeNode.leftNode, function)
        preOrderTraverseTree(treeNode.rightNode, function)
    }
}

Both traversal methods use recursion. The function parameter is a callback that gets called for each node value, which is a nice pattern. You can pass in any function like fmt.Println or a custom handler.

Searching

The Search method checks if all provided tree nodes exist in the set. It returns false as soon as one is missing:

func (treeset *TreeSet) Search(treeNodes ...TreeNode) bool {
    var treeNode TreeNode
    var exists bool
    for _, treeNode = range treeNodes {
        if exists = treeset.bst.SearchNode(treeNode.key); !exists {
            return false
        }
    }
    return true
}

The String Method

For printing the TreeSet:

func (treeset *TreeSet) String() {
    treeset.bst.String()
}

Using a TreeSet

Here’s the complete example:

func main() {
    var treeset *TreeSet = &TreeSet{}
    treeset.bst = &BinarySearchTree{}
    var node1 TreeNode = TreeNode{8, 8, nil, nil}
    var node2 TreeNode = TreeNode{3, 3, nil, nil}
    var node3 TreeNode = TreeNode{10, 10, nil, nil}
    var node4 TreeNode = TreeNode{1, 1, nil, nil}
    var node5 TreeNode = TreeNode{6, 6, nil, nil}
    treeset.InsertTreeNode(node1, node2, node3, node4, node5)
    treeset.String()
}

You build it with go build treeset.go binarysearchtree.go since the TreeSet depends on the BST implementation from earlier in the book.

Synchronized TreeSets

When multiple goroutines need to access the same TreeSet, you need synchronization. The book handles this the same way as the dictionary, using sync.RWMutex.

The InsertElement method on the BST acquires a write lock before modifying the tree:

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 pattern is the same everywhere: lock before writing, read-lock before reading, defer the unlock. This is Go’s standard approach to concurrent data structure access.

Mutable TreeSets

A mutable TreeSet supports add, update, and delete operations. The insertTreeNode function handles the actual tree insertion logic, recursively finding the right spot based on the key:

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)
        }
    }
}

If the new key is smaller than the current node’s key, go left. If it’s bigger (or equal), go right. Keep going until you find an empty spot. This is standard binary search tree insertion.

The RemoveNode method follows the same locking pattern:

func (tree *BinarySearchTree) RemoveNode(key int) {
    tree.lock.Lock()
    defer tree.lock.Unlock()
    removeNode(tree.rootNode, key)
}

You can also update nodes by traversing through treeset.bst and accessing the root node and its left and right children directly.

Key Takeaways

A few things to remember from this part of Chapter 7:

1. Dictionaries are key-value stores. Go’s built-in map does the same thing, but building one from scratch teaches you how locking and concurrent access work.

2. TreeSets keep elements sorted and unique using a binary search tree. Operations cost O(log n), which is efficient for most use cases.

3. Synchronization in Go comes down to sync.RWMutex. Use Lock/Unlock for writes, RLock/RUnlock for reads. This lets multiple readers access data at the same time without blocking each other.

4. The defer pattern for unlocking is everywhere in Go concurrent code. It’s clean and prevents you from accidentally leaving a lock held if something goes wrong.

In Part 2, we’ll look at sequences: Farey, Fibonacci, look-and-say, and Thue-Morse. Those are more math-oriented but still interesting to implement in Go.

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). The ideas and code examples are from the book, explained in my own words.