DFS explores every subtree until it hits a dead end before switching to another path. It can be done recursively, or it can be done iteratively. Let’s reuse the TreeNode definition from our BFS post. 1. Recursive Solution The recursive approach achieves O(n)O(n) time in the worst case, O(logn)O(\log n) space in the best case,… Continue reading Depth-First Search (DFS)
Tag: generic
Binary Heap
A binary heap is a complete binary tree that maintains the heap property: every parent is either less than or equal to its children (min-heap), or greater than or equal to its children (max-heap). Binary heaps are commonly used to implement priority queues (an abstract data type that finds its highest-priority item in O(1)O(1) time),… Continue reading Binary Heap
Breadth-First Search (BFS)
Suppose you’re given a binary tree implemented somewhat like this: Breadth-First Search (BFS) means you traverse the tree level by level, not diving deep into a child node every chance you get. The blocker here is not knowing how to link all nodes belonging to the same level, because in a binary tree, same-level nodes… Continue reading Breadth-First Search (BFS)
Binary Search
Binary Search I know, the word binary screams binary tree. But no, binary search doesn’t require a tree at all. It’s usually implemented in an array. In Go, we can simply use a slice to do this. Note that a binary search can only be performed on a sorted array. The generic signature [S ~[]E,… Continue reading Binary Search
Stack & Queue in Go
1. Stack This is your good ol’ LIFO (last-in, first-out) structure. Just imagine a Pringles tube. A basic stack should have the following methods: In Go, you can use a slice as the underlying data structure. Notice how initiating the store slice in the NewStack[T any]() constructor is optional? This is because we have enough… Continue reading Stack & Queue in Go
Frequency map in Go
A frequency map is just a fancy word for a hash map that tracks the number of occurrences of an element in a collection. If we have a slice in Go and we want to know exactly how many times each element in the slice occurs in the slice, we can build a frequency map… Continue reading Frequency map in Go
Map-as-Set in Go
In programming languages like Go, there is no built-in type for set. A set essentially answers yes or no: is a given element present? We can use the built-in map type to implement sets. I used to implement map-as-set like this: Apparently, Gemini thinks there’s a better way: Gemini thinks this is better because it… Continue reading Map-as-Set in Go