Golang DSA Chapter 7 Part 2: Sequences and Anti-Patterns
Welcome back. In Part 1 we went through dictionaries and TreeSets. This second half of Chapter 7 wraps up TreeSets with synchronized and mutable variants, then moves into some cool mathematical sequences implemented in Go. We also talk about common anti-patterns the book warns about when working with these data structures.
Let’s get to it.
Synchronized TreeSets
When you have multiple goroutines reading and writing to a TreeSet at the same time, things can go sideways fast. The book’s solution is straightforward: use sync.RWMutex to lock the tree during insert, delete, and update operations.
Here’s what a synchronized insert looks like:
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 simple: lock at the start, defer the unlock, then do your work. The defer keyword makes sure the lock gets released no matter what happens in the function body. Same idea applies to RemoveNode:
func (tree *BinarySearchTree) RemoveNode(key int) {
tree.lock.Lock()
defer tree.lock.Unlock()
removeNode(tree.rootNode, key)
}
Nothing fancy. Just discipline with your locks.
Mutable TreeSets
Mutable TreeSets support add, update, and delete operations. The recursive insertTreeNode function handles placing new nodes in the right 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)
}
}
}
If the new key is smaller, go left. If it’s bigger (or equal), go right. Keep going until you find an empty spot. Classic binary search tree insertion.
You interact with it through the TreeSet wrapper:
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()
Sequences
Now we get to the fun part. A sequence is just a set of numbers grouped in a specific order. If the sequence can go on forever, it’s called a stream. A subsequence is what you get when you take a sequence and remove some elements while keeping the rest in their original order.
The book covers four types: Farey, Fibonacci, look-and-say, and Thue-Morse.
Farey Sequence
The Farey sequence is a list of reduced fractions between 0 and 1, where all the denominators are at most some number m. They’re arranged in ascending order.
First, a simple fraction struct:
type fraction struct {
numerator int
denominator int
}
func (frac fraction) String() string {
return fmt.Sprintf("%d/%d", frac.numerator, frac.denominator)
}
The clever part is the g function. It recursively generates the Farey series by taking two bounding fractions and producing the mediants (fractions formed by adding the numerators and denominators separately):
func g(l fraction, r fraction, num int) {
var frac fraction
frac = fraction{l.numerator + r.numerator, l.denominator + r.denominator}
if frac.denominator <= num {
g(l, frac, num)
fmt.Print(frac, " ")
g(frac, r, num)
}
}
The main function generates Farey sequences from F(1) through F(11):
func main() {
var num int
var l fraction
var r fraction
for num = 1; num <= 11; num++ {
l = fraction{0, 1}
r = fraction{1, 1}
fmt.Printf("F(%d): %s ", num, l)
g(l, r, num)
fmt.Println(r)
}
}
So F(1) is just 0/1 and 1/1. F(2) adds 1/2 in between. F(3) adds 1/3 and 2/3. Each level gets more fractions squeezed in. It’s kind of beautiful how the recursion handles this naturally.
Fibonacci Sequence
You’ve probably seen this one before. Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…
Fun fact the book mentions: Pingala described these numbers way back in 200 BC, long before Fibonacci made them famous in Europe.
The book shows two approaches. First, the iterative Series function that builds up an array:
func Series(n int) int {
var f []int
f = make([]int, n+1, n+2)
if n < 2 {
f = f[0:2]
}
f[0] = 0
f[1] = 1
var i int
for i = 2; i <= n; i++ {
f[i] = f[i-1] + f[i-2]
}
return f[n]
}
Then the recursive version, which is cleaner but way slower for large numbers:
func FibonacciNumber(n int) int {
if n <= 1 {
return n
}
return FibonacciNumber(n-1) + FibonacciNumber(n-2)
}
Both give the same results. The main function runs them side by side:
func main() {
var i int
for i = 0; i <= 9; i++ {
fmt.Print(strconv.Itoa(Series(i)) + " ")
}
fmt.Println("")
for i = 0; i <= 9; i++ {
fmt.Print(strconv.Itoa(FibonacciNumber(i)) + " ")
}
fmt.Println("")
}
Output for both: 0 1 1 2 3 5 8 13 21 34
The iterative version is O(n) time and O(n) space. The recursive version is O(2^n) time because it recalculates the same values over and over. For anything beyond small inputs, use the iterative approach. The book also mentions that Fibonacci numbers show up in search algorithms, heap data structures, and pseudorandom number generators.
Look-and-Say Sequence
This is one of those sequences that sounds confusing until it clicks. Coined by John Conway, you generate each term by literally describing what you see in the previous term.
Start with “1”. You see one 1, so the next term is “11”. Then you see two 1s, so it becomes “21”. Then one 2 and one 1, giving “1211”. And so on:
1, 11, 21, 1211, 111221, 312211…
The Go implementation walks through each character, counting consecutive identical digits:
func look_say(str string) (rstr string) {
var cbyte byte
cbyte = str[0]
var inc int
inc = 1
var i int
for i = 1; i < len(str); i++ {
var dbyte byte
dbyte = str[i]
if dbyte == cbyte {
inc++
continue
}
rstr = rstr + strconv.Itoa(inc) + string(cbyte)
cbyte = dbyte
inc = 1
}
return rstr + strconv.Itoa(inc) + string(cbyte)
}
The main function seeds it with “1” and runs 8 iterations:
func main() {
var str string
str = "1"
fmt.Println(str)
var i int
for i = 0; i < 8; i++ {
str = look_say(str)
fmt.Println(str)
}
}
Each term grows roughly 30% longer than the previous one (Conway proved the growth rate converges to about 1.303577…), so the strings get big quickly.
Thue-Morse Sequence
The Thue-Morse sequence is a binary sequence that starts with 0, then keeps appending the Boolean complement of what you have so far.
- Start: 0
- Flip it, append: 01
- Flip “01” to “10”, append: 0110
- Flip “0110” to “1001”, append: 01101001
- And so on…
It’s used in combinatorics and shows up in fractal curves like Koch snowflakes.
The Go code uses bytes.Buffer and flips each existing byte to build the next iteration:
func ThueMorseSequence(buffer *bytes.Buffer) {
var b int
var currLength int
var currBytes []byte
for b, currLength, currBytes = 0, buffer.Len(), buffer.Bytes(); b < currLength; b++ {
if currBytes[b] == '1' {
buffer.WriteByte('0')
} else {
buffer.WriteByte('1')
}
}
}
func main() {
var buffer bytes.Buffer
buffer.WriteByte('0')
fmt.Println(buffer.String())
var i int
for i = 2; i <= 7; i++ {
ThueMorseSequence(&buffer)
fmt.Println(buffer.String())
}
}
Notice how currLength is captured before the loop starts. That’s important, because the buffer grows during iteration. Without capturing the length first, you’d end up in an infinite loop. Small detail, big consequence.
Anti-Patterns to Watch For
The book mentions anti-patterns for dictionaries, TreeSets, and sequences. Based on the patterns shown throughout the chapter, here are the common mistakes to avoid:
Dictionary anti-patterns:
- Not checking if a key exists before accessing it. In Go, reading a missing key from a map gives you a zero value silently, which can cause subtle bugs. Always use the two-value form:
val, ok := myMap[key]. - Using mutable types as map keys. Stick to strings, ints, or other comparable types.
- Forgetting that Go maps are not safe for concurrent access. If multiple goroutines touch the same map, you need a mutex or
sync.Map.
TreeSet anti-patterns:
- Skipping synchronization in concurrent scenarios. The book explicitly shows how to use
sync.RWMutexfor a reason. If you share a TreeSet across goroutines without locking, you’ll get race conditions. - Not using
deferfor unlocking. If your function panics or returns early without unlocking, you deadlock the whole tree. - Inserting duplicate keys without a clear strategy. The book’s
insertTreeNodeputs equal keys to the right, but you should be intentional about this in your own code.
Sequence anti-patterns:
- Using the naive recursive Fibonacci for large inputs. It’s O(2^n) and will absolutely crush your performance. Use the iterative version or memoization.
- String concatenation in a loop (like the look-and-say example does with
rstr + ...). For production code, usestrings.Builderinstead. Each+creates a new string in Go, so this gets expensive fast. - Not capturing buffer length before iterating (like the Thue-Morse example carefully does). Modifying a collection while iterating over it is a classic source of bugs.
Chapter 7 Wrap-Up
This chapter covered a lot of ground across both parts. Dictionaries, TreeSets with synchronization, and four different mathematical sequences, each with a clean Go implementation. The sequences section is a nice break from the more practical data structures. They’re the kind of problems that make you appreciate how recursion can express complex patterns in just a few lines of code.
The questions at the end of the chapter test whether you understood the fundamentals: how to synchronize a BST, what defer does, how to convert between types, and the basics of each sequence type.
Up next, Chapter 8 gets into sorting algorithms. That’s where things get really practical.