DSA - Data Structures and Algorithms

🧠 Mastering Data Structures and Algorithms (DSA) with `Go` and its `Python` Counterpart

Whether you’re preparing for technical interviews, optimizing backend systems, or simply sharpening your problem-solving chops, Data Structures and Algorithms (DSA) are foundational to your success as a developer.

In this article, I’ll walk you through core DSA concepts using Golang and Python, a language praised for its simplicity, performance, and concurrency model. You’ll see how Go makes understanding DSA both intuitive and powerful.

🚀 What is DSA?

Data Structures organize and store data efficiently, while Algorithms define step-by-step instructions to solve problems or manipulate data.

Together, DSA provides the backbone for high-performance applications.

📦 Essential Data Structures in `Go` and its `Python` Counterpart

Arrays & Slices

Go implementation:

1
2
3
4
5
arr := [5]int{1, 2, 3, 4, 5} // Fixed-size array
slice := []int{1, 2, 3}      // Dynamic size

slice = append(slice, 4)
fmt.Println(slice) // [1 2 3 4]

Python implementation:

1
2
3
 arr = [1, 2, 3, 4, 5]  # Dynamic array (list in Python)
 arr.append(6)
 print(arr)  # [1, 2, 3, 4, 5, 6]

Slices are the idiomatic way to work with collections in Go. They offer flexibility while leveraging arrays under the hood.

Linked List

Go doesn’t have a built-in linked list, but the container/list package provides one.

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
package main

import (
"container/list"
"fmt"
)

func main() {
l := list.New()
l.PushBack("Go")
l.PushBack("DSA")

    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }
}

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 class Node:
     def __init__(self, data):
         self.data = data
         self.next = None

 class LinkedList:
     def __init__(self):
         self.head = None

     def append(self, data):
         new_node = Node(data)
         if not self.head:
             self.head = new_node
             return
         last = self.head
         while last.next:
             last = last.next
         last.next = new_node

     def print_list(self):
         current = self.head
         while current:
             print(current.data)
             current = current.next

 ll = LinkedList()
 ll.append("Python")
 ll.append("DSA")
 ll.print_list()

Stack (LIFO)

A stack can be easily implemented using slices.

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
type Stack []int

func (s *Stack) Push(v int) {
    *s = append(*s, v)
}

func (s *Stack) Pop() int {
    n := len(*s)
    val := (*s)[n-1]
    *s = (*s)[:n-1]
    return val
}

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 class Stack:
       def __init__(self):
             self.stack = []

       def push(self, item):
             self.stack.append(item)  # append to the end (like Go's append)

       def pop(self):
             if not self.stack:
              raise IndexError("pop from empty stack")
             return self.stack.pop()  # pop from the end (like Go's slice)

Queue (FIFO)

Queues can also be implemented using slices.

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
type Queue []int

func (q *Queue) Enqueue(v int) {
    *q = append(*q, v)
}

func (q *Queue) Dequeue() int {
    val := (*q)[0]
    *q = (*q)[1:]
    return val
}

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Queue:
     def __init__(self):
         self.queue = []

     def enqueue(self, item):
         # append to the end (like Go's append)
         self.queue.append(item)

     def dequeue(self):
         if not self.queue:
             raise IndexError("dequeue from empty queue")
         # take from the front (like q[0] in Go)
         val = self.queue[0]
         self.queue = self.queue[1:]  # shrink list (like Go slice)
         return val

Hash Map (Go's map)

Go implementation:

1
2
3
4
5
m := map[string]int{
    "apple":  5,
    "banana": 3,
}
fmt.Println(m["apple"]) // 5

Hint: Go’s built-in map is a powerful hash table implementation for key-value pairs.

🔑 What types can be keys in a Go map?

A map key must be comparable (Go requires == and != operators to be defined).
✅ Allowed key types:
- Booleans (bool)
- Numbers (int, float64, etc.)
- Strings
- Pointers
- Channels
- Interfaces (if the underlying type is comparable)
- Structs (if all their fields are comparable)
- Arrays (fixed-size, if elements are comparable)
❌ Not allowed as keys:
- Slices
- Maps
- Functions

These types are not comparable in Go, so they cannot be used as map keys.

Example:

1
2
3
4
5
6
7
8
9
// Valid keys
m1 := map[int]string{1: "one", 2: "two"}
m2 := map[bool]string{true: "yes", false: "no"}
m3 := map[[2]int]string{{1, 2}: "coords"} // array key
m4 := map[struct{ID int}]string{{ID: 1}: "first"} // struct key

fmt.Println(m1[1]) // "one"
fmt.Println(m2[false]) // "no"
fmt.Println(m3[[2]int{1, 2}]) // "coords"

If you try with a slice:

1
m := map[[]int]string{}

👉 You’ll get a compile-time error:

1
invalid map key type []int

✅ Summary:

Go maps work with keys of any type that is comparable.
Commonly: string, int, bool, structs, and arrays.
Not allowed: slices, maps, functions.

Python implementation:

1
2
3
4
5
 m = {
     "apple": 5,
     "banana": 3,
 }
 print(m["apple"])  # 5

🔑 What types can be keys in a Python dict?

A key must be hashable → meaning it has a valid hash() and does not change during its lifetime.
✅ Allowed key types:
- Immutable built-ins: str, int, float, bool, bytes
- Tuples (if all elements are hashable)
- frozenset (immutable version of set`)
- User-defined classes (if they implement hash and eq)
❌ Not allowed as keys:
- Mutable types like list, dict, and set
- These can change after being used as a key, which would break hash table invariants.

Example:

1
2
3
4
5
6
7
8
9
# Valid keys
m1 = {1: "one", 2: "two"}                 # int keys
m2 = {True: "yes", False: "no"}           # bool keys
m3 = {(1, 2): "coords"}                   # tuple key
m4 = {frozenset([1, 2]): "frozen set"}    # frozenset key

print(m1[1])         # "one"
print(m2[False])     # "no"
print(m3[(1, 2)])    # "coords"

If you try with a list:

1
m = { [1, 2]: "coords" }

👉 You’ll get a runtime error:

1
TypeError: unhashable type: 'list'

✅ Summary:

Python dicts require keys to be hashable.
Commonly: strings, numbers, booleans, tuples of immutables, frozensets.
Not allowed: lists, dicts, sets (mutable types).

🧩 Must-Know Algorithms in `Go`

Binary Search

Efficient O(log n) search on sorted arrays.

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1

    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 def binary_search(arr, target):
      low, high = 0, len(arr) - 1
      while low <= high:
           mid = (low + high) // 2
           if arr[mid] == target:
                return mid
           elif arr[mid] < target:
                low = mid + 1
           else:
                high = mid - 1
      return -1

Sorting (Bubble Sort Example)

Video explanation: Bubble Sort Algorithm

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

Python implementation:

1
2
3
4
5
6
 def bubble_sort(arr):
     n = len(arr)
     for i in range(n):
         for j in range(0, n-i-1):
             if arr[j] > arr[j+1]:
                 arr[j], arr[j+1] = arr[j+1], arr[j]

For real projects, use Go’s built-in sorting:

1
sort.Ints(arr)

Recursion: Factorial

Factorial of n (n!) is the product of all positive integers up to n.

Go implementation:

1
2
3
4
5
6
7
func factorial(n int) int {
    if n == 0 {
    return 1
    }

    return n * factorial(n-1)
}

Python implementation:

1
2
3
4
 def factorial(n):
      if n == 0:
           return 1
      return n * factorial(n-1)

Example: The factorial of 4 is 4 * 3 * 2 * 1 = 24.

1
2
3
4
5
6
7
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))
= 24

Fibonacci Sequence

Fibonacci numbers are the sum of the two preceding ones, starting from 0 and 1.

Go implementation:

1
2
3
4
5
6
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

Python implementation:

1
2
3
4
 def fibonacci(n):
      if n <= 1:
           return n
      return fibonacci(n-1) + fibonacci(n-2)

Example: The sequence starts as: 0, 1, 1, 2, 3, 5, 8, 13, …

1
2
3
4
5
6
7
fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + (fibonacci(1) + 1)
= (((fibonacci(1) + fibonacci(0)) + 1) + (1 + 0)) + (1 + 1)
= (((1 + 0) + 1) + 1) + 2
= 5

Prime Check

Prime numbers are greater than 1 and only divisible by 1 and themselves.

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func isPrime(n int) bool {
    if n <= 1 {
        return false
    }
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

Python implementation:

1
2
3
4
5
6
7
8
9
 from math import sqrt

 def is_prime(n):
      if n <= 1:
           return False
      for i in range(2, int(sqrt(n)) + 1):
           if n % i == 0:
             return False
      return True

Example: The number 11 is prime, while 12 is not.

1
2
3
4
5
isPrime(11)
= true (11 is only divisible by 1 and 11)

isPrime(12)
= false (12 is divisible by 1, 2, 3, 4, 6, and 12)

FizzBuzz :)

A classic programming challenge.

Go implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func fizzBuzz(n int) {
    for i := 1; i <= n; i++ {
        if i%3 == 0 && i%5 == 0 {
            fmt.Println("FizzBuzz")
        } else if i%3 == 0 {
            fmt.Println("Fizz")
        } else if i%5 == 0 {
            fmt.Println("Buzz")
        } else {
            fmt.Println(i)
        }
    }
}

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def fizz_buzz(n):
    for i in range(1, n + 1):
        if i % 3 == 0 and i % 5 == 0:
            print("FizzBuzz")
        elif i % 3 == 0:
            print("Fizz")
        elif i % 5 == 0:
            print("Buzz")
        else:
            print(i)

Example: For n = 15 print the numbers from 1 to 15. For multiples of 3, print “Fizz” instead of the number. For multiples of 5, print “Buzz”. For numbers which are multiples of both 3 and 5, print “FizzBuzz”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 1
 2
 Fizz
 4
 Buzz
 Fizz
 7
 8
 Fizz
 Buzz
 11
 Fizz
 13
 14
 FizzBuzz

Graph and Trees

For binary trees, you define custom structures.

Go implementation:

1
2
3
4
5
type Node struct {
Value int
Left  *Node
Right *Node
}

Python implementation:

1
2
3
4
5
 class Node:
       def __init__(self, value):
             self.value = value
             self.left = None
             self.right = None

Depth-first traversal:

Go implementation:

1
2
3
4
5
6
7
8
9
func dfs(n *Node) {
    if n == nil {
        return
    }

    fmt.Println(n.Value)
    dfs(n.Left)
    dfs(n.Right)
}

Python implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Node:
 def __init__(self, value):
     self.value = value
     self.left = None
     self.right = None

def dfs(node):
     if node is None:
         return

    print(node.value)      # Preorder: visit root
    dfs(node.left)         # Traverse left subtree
    dfs(node.right)        # Traverse right subtree

🔃 Sort Algorithms

Sorting is a fundamental concept in computer science used in everything from searching to data normalization and ranking systems. Below are essential sorting algorithms every developer should know, implemented in Go.

Merge Sort (🧬 Divide and Conquer – O(n log n))

Merge Sort recursively splits arrays into halves and merges them in a sorted manner.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    return append(result, append(left[i:], right[j:]...)...)
}

Quick Sort (⚡ Partition-based – Average: O(n log n), Worst: O(n²))

Quick Sort selects a pivot and partitions the array into smaller and larger elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func quickSort(arr []int) {
    if len(arr) < 2 {
        return
    }

    left, right := 0, len(arr)-1
    pivot := rand.Int() % len(arr)
    arr[pivot], arr[right] = arr[right], arr[pivot]

    for i := range arr {
        if arr[i] < arr[right] {
            arr[i], arr[left] = arr[left], arr[i]
            left++
        }
    }

    arr[left], arr[right] = arr[right], arr[left]
    quickSort(arr[:left])
    quickSort(arr[left+1:])
}

Bubble Sort (🫧 Simple but Inefficient – O(n²))

Repeatedly swaps adjacent elements if they are in the wrong order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

Insertion Sort (🧩 Efficient for Small Datasets – O(n²))

Builds the sorted array one item at a time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

Selection Sort (📌 Selects Minimum – O(n²))

Repeatedly finds the minimum element and places it at the beginning.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

Heap Sort (🏗️ Priority Queue-based – O(n log n))

Uses a binary heap structure to repeatedly extract the max element.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func heapSort(arr []int) {
    n := len(arr)

    // Build max heap
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

Each of these sorting algorithms serves different use cases. While Go’s sort package provides optimized versions, understanding how these work internally is critical for building performance-conscious software.

📑 Sorting Algorithms - Cheat Sheet

Algorithm	Best Time	Avg Time	Worst Time	Space	Stable	In-Place	Notes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ Yes	❌ No	Divide and conquer, great for linked lists
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌ No	✅ Yes	Very fast in practice, not stable
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes	✅ Yes	Educational use only, very slow
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes	✅ Yes	Efficient for small or nearly sorted data
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌ No	✅ Yes	Always O(n²), rarely used
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ No	✅ Yes	Good for priority queues

✅ Stable: Maintains the relative order of equal elements
✅ In-Place: Uses constant extra space (excluding recursion stack)

🔍 Search Algorithms

Search algorithms are foundational tools in computer science used to retrieve information stored in data structures like arrays, trees, or graphs. Whether you’re working with sorted arrays, exploring hierarchical structures, or traversing complex graphs, the right search algorithm can dramatically improve efficiency and performance.

Let’s dive into three essential search algorithms and their Go implementations:

🧭 Binary Search

Use Case: Efficiently search for a value in a sorted array. Time Complexity: O(log n) Space Complexity: O(1) (iterative), O(log n) (recursive)

Concept: Binary Search divides the array into halves, eliminating one half at each step, depending on whether the target is greater or smaller than the midpoint.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func BinarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // not found
}

🌐 Breadth-First Search (BFS)

Use Case: Traverse or search tree/graph level by level. Ideal for finding the shortest path in unweighted graphs. Time Complexity: O(V + E) (vertices + edges) Space Complexity: O(V)

Concept: BFS uses a queue to explore all neighboring nodes before going deeper. It’s a level-order traversal for trees or graphs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func BFS(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    result := []int{}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if visited[node] {
            continue
        }
        visited[node] = true
        result = append(result, node)

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                queue = append(queue, neighbor)
            }
        }
    }
    return result
}

🧱 Depth-First Search (DFS)

Use Case: Explore all paths or check for connectivity in graphs/trees. Great for scenarios like maze-solving, backtracking, and topological sorting. Time Complexity: O(V + E) Space Complexity: O(V) (recursive stack or visited map)

Concept: DFS explores as far as possible along each branch before backtracking. Implemented with recursion or a stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func DFS(graph map[int][]int, start int, visited map[int]bool, result *[]int) {
    if visited[start] {
        return
    }
    visited[start] = true
    *result = append(*result, start)

    for _, neighbor := range graph[start] {
        if !visited[neighbor] {
            DFS(graph, neighbor, visited, result)
        }
    }
}

To initiate DFS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
graph := map[int][]int{
    1: {2, 3},
    2: {4},
    3: {},
    4: {},
}
visited := make(map[int]bool)
result := []int{}
DFS(graph, 1, visited, &result)
fmt.Println(result) // Output: [1 2 4 3] (DFS order may vary)

🔍 Search Algorithms – Cheat Sheet

Algorithm	Use Case	Time Complexity	Space Complexity	Notes
Binary Search	Search in sorted arrays	O(log n)	O(1) (iterative) O(log n) (recursive)	Requires sorted input
Breadth-First Search (BFS)	Shortest path in unweighted graphs	O(V + E)	O(V)	Level-order traversal, uses a queue
Depth-First Search (DFS)	Exploring all paths, topological sort, cycle detection	O(V + E)	O(V)	Preorder traversal, uses recursion or stack

🌳 Tree Traversal Algorithms

Traversing a tree means visiting every node in a specific order. Whether you’re parsing expressions, printing a binary tree, or converting structures, understanding traversal strategies is fundamental in computer science.

This guide covers the four most common tree traversal algorithms:

Pre-Order Traversal
In-Order Traversal
Post-Order Traversal
Level-Order Traversal

📐 Tree Node Definition in Go
Before diving into each traversal, here’s the standard binary tree structure we’ll use:
1 2 3 4 5
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }

🔁 Pre-Order Traversal (Root → Left → Right)

Use Case: Useful for copying a tree or prefix expression evaluation.

Steps:

Visit root
Traverse left subtree
Traverse right subtree

1
2
3
4
5
6
7
8
func PreOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    *result = append(*result, node.Val)
    PreOrder(node.Left, result)
    PreOrder(node.Right, result)
}

📏 In-Order Traversal (Left → Root → Right)

Use Case: Yields nodes in ascending order for Binary Search Trees (BST).

Steps:

Traverse left subtree
Visit root
Traverse right subtree

1
2
3
4
5
6
7
8
func InOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    InOrder(node.Left, result)
    *result = append(*result, node.Val)
    InOrder(node.Right, result)
}

🧮 Post-Order Traversal (Left → Right → Root)

Use Case: Ideal for deleting or freeing nodes, postfix expression evaluation.

Steps:

Traverse left subtree
Traverse right subtree
Visit root

1
2
3
4
5
6
7
8
func PostOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    PostOrder(node.Left, result)
    PostOrder(node.Right, result)
    *result = append(*result, node.Val)
}

🏛️ Level-Order Traversal (Breadth-First)

Use Case: Used for printing trees by level or finding the shortest path in a tree.

Steps:

Traverse nodes level by level (left to right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func LevelOrder(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}
    var result []int

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node.Val)

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return result
}

🔧 Test Tree Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Construct the following tree:
//      1
//     / \
//    2   3
//   / \   \
//  4   5   6

root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Left.Right = &TreeNode{Val: 5}
root.Right.Right = &TreeNode{Val: 6}

var pre, in, post []int
PreOrder(root, &pre)
InOrder(root, &in)
PostOrder(root, &post)
level := LevelOrder(root)

fmt.Println("Pre-Order:", pre)    // [1 2 4 5 3 6]
fmt.Println("In-Order:", in)      // [4 2 5 1 3 6]
fmt.Println("Post-Order:", post)  // [4 5 2 6 3 1]
fmt.Println("Level-Order:", level)// [1 2 3 4 5 6]

⚙️ Quick Go Snippets

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Pre-Order Traversal
func PreOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    *result = append(*result, node.Val)
    PreOrder(node.Left, result)
    PreOrder(node.Right, result)
}

// In-Order Traversal
func InOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    InOrder(node.Left, result)
    *result = append(*result, node.Val)
    InOrder(node.Right, result)
}

// Post-Order Traversal
func PostOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }
    PostOrder(node.Left, result)
    PostOrder(node.Right, result)
    *result = append(*result, node.Val)
}

// Level-Order Traversal (BFS)
func LevelOrder(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    queue := []*TreeNode{root}
    var result []int

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node.Val)

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return result
}

🌳 Tree Traversal Algorithms – Cheat Sheet

Traversal Type	Visit Order	Use Case	Time Complexity	Space Complexity
Pre-Order	Root → Left → Right	Copy tree, prefix expressions	O(n)	O(h)
In-Order	Left → Root → Right	Sorted output in BSTs	O(n)	O(h)
Post-Order	Left → Right → Root	Delete tree, postfix expressions	O(n)	O(h)
Level-Order	Level by level (BFS)	Print by level, shortest path	O(n)	O(w)

Legend:

n: number of nodes
h: tree height (log n for balanced, n for skewed)
w: max width of the tree (can be up to n/2 in balanced trees)

➗ The Modulo Operator (%)

The modulo operator is often underestimated, but it’s a fundamental tool in both algorithm design and real-world programming.

What Is Modulo?

a % b returns the remainder after dividing a by b.

1
a = b × q + r where 0 ≤ r < b

Example: 5 % 2 = 1
Example: 12 % 5 = 2
Example: 20 % 5 = 0

👉 If a < b, then a % b = a.

When Do We Use Modulo?

Checking Divisibility

It is used to check if a number is even or odd.

Go implementation:

1
2
3
4
5
if n%2 == 0 {
    fmt.Println("Even")
} else {
    fmt.Println("Odd")
}

Python implementation:

1
2
3
4
if n % 2 == 0:
    print("Even")
else:
    print("Odd")

Cyclic Patterns (wrap-around

Go implementation:

1
2
3
days := []string{"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"}
dayIndex := (currentDay + offset) % 7
fmt.Println(days[dayIndex])

Python implementation:

1
2
3
days = ["Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"]
day_index = (current_day + offset) % 7
print(days[day_index])

🔄 Example Walkthrough

Let’s say today is Friday (currentDay = 5).

Offset = 2 (2 days later):
1 2
(5 + 2) % 7 = 7 % 7 = 0 days[0] = "Sun"
✅ Two days after Friday is Sunday.
Offset = 10 (10 days later):
1 2
(5 + 10) % 7 = 15 % 7 = 1 days[1] = "Mon"
✅ Ten days after Friday is Monday.
Offset = -3 (3 days earlier):
1 2
(5 - 3) % 7 = 2 % 7 = 2 days[2] = "Tue"
✅ Three days before Friday is Tuesday.

Rotating Arrays
Array rotation is the process of shifting elements circularly — so elements that “fall off” one end reappear on the other end.
This is common in:
- Coding interview problems (LeetCode, HackerRank).
- Scheduling (round-robin tasks).
- Games & simulations (rotating positions, cyclic states).
- Data processing (moving averages, cyclic windows).
Go implementation:
1 2 3 4 5
func rotate(arr []int, k int) []int { n := len(arr) k = k % n // handle k > n return append(arr[n-k:], arr[:n-k]...) }
Python implementation:
1 2 3 4
def rotate(arr, k): n = len(arr) k = k % n # handle k > n return arr[-k:] + arr[:-k]
- n := len(arr) → length of the array.
- k = k % n → ensures we don’t rotate more than necessary (e.g., rotating 12 times on length 5 = same as rotating 2 times).
- arr[n-k:] → last k elements (to move to front).
- arr[:n-k] → first n-k elements (move after).
- `appen → combines into rotated array.
🔄 Example Walkthrough
1 2 3 4
arr := []int{1, 2, 3, 4, 5} k := 2 res := rotate(arr, k) fmt.Println(res)
Steps:
- Original: [1 2 3 4 5]
- Split: last 2 elements → [4 5], first 3 elements → [1 2 3]
- Append: [4 5 1 2 3]
✅ Result: [4 5 1 2 3]
🔄 Another Example (k > n)
1 2 3 4
arr := []int{10, 20, 30, 40, 50} k := 7 res := rotate(arr, k) fmt.Println(res)
- n = 5
- k = 7 % 5 = 2
- Split: last 2 → [40 50], first 3 → [10 20 30]
- Result: [40 50 10 20 30]
🧭 Left vs Right Rotations
- Above code rotates to the right (end → front).
- To rotate left, just swap the slices:
1 2 3 4 5
func rotateLeft(arr []int, k int) []int { n := len(arr) k = k % n return append(arr[k:], arr[:k]...) }
✅ Key Takeaway: Array rotation is a simple but powerful trick for cyclic problems. In Go, slicing + append makes it elegant and efficient.
📌 Use Cases
- Round-Robin Scheduling → rotate task queue.
- Cipher Algorithms → shift characters cyclically.
- Sliding Window Problems → rotate buffers instead of reallocating.
- Gaming → rotate players’ turns.

Hashing

Hashing is the process of taking a large (potentially infinite) set of input keys and mapping them into a fixed range of slots. This is crucial for data structures like hash tables, maps, and sets, where we want fast lookup, insert, and delete operations.

The main idea:

We have more possible keys than storage slots.
We apply a hash function that always outputs a value within [0 … tableSize-1].
This allows us to place data into a fixed-size array and still find it later in constant time.

Go implementation:

1
hash := (key % tableSize + tableSize) % tableSize // handle negative keys

Output:

1
2
3
4
Key 12     → Slot 2
Key 99     → Slot 4
Key -7     → Slot 3
Key 123456 → Slot 1

Python implementation:

1
hash = (key % table_size + table_size) % table_size  # handle negative keys

1.1 🛠️ Why Hashing Matters

Efficiency: Lookup/insert/delete in O(1) on average.
Fixed memory: No need for huge arrays, even if keys are massive.
Determinism: Same key → always the same slot.

👉 No matter how large or negative the key is, the result always lands in [0,4] because the table size is 5.

1.2 ⚠️ The Collision Problem

Since the number of possible keys is much larger than the number of slots, different keys may map to the same slot. Example:

- 12 % 5 = 2

- 22 % 5 = 2

Both keys → slot 2.

Common strategies to handle this:

Chaining – each slot stores a linked list or slice of elements.
Open Addressing – if a slot is taken, probe for the next free one (linear probing, quadratic probing, double hashing).

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
package main

import "fmt"

func main() {
tableSize := 5
table := make([][]int, tableSize) // slice of buckets (chaining)

    keys := []int{12, 22, 99, -7}
    for _, key := range keys {
        idx := (key % tableSize + tableSize) % tableSize
        table[idx] = append(table[idx], key) // put key into bucket
    }

    // 🔍 Lookup
    keyToFind := 22
    idx := (keyToFind % tableSize + tableSize) % tableSize
    fmt.Println("Looking for key:", keyToFind, "in bucket:", idx)
    fmt.Println("Bucket contents:", table[idx])
}

Output:

1
2
Looking for key: 22 in bucket: 2
Bucket contents: [12 22]

1.3 ✅ Key Takeaway

Hashing ensures that any key, no matter how large or small, is mapped into a fixed range of slots. This is what makes hash maps and sets in Go (and other languages) efficient and practical.

1.4 🚀 Hashing in Real Go Code (map)

In real-world Go code, you don’t usually implement hashing yourself — you just use the built-in map.

1
2
3
4
5
6
users := map[int]string{
 123: "Alice",
 456: "Bob",
}

fmt.Println(users[123]) // "Alice"

Go’s map already:

- Computes the hash of your keys.

- Decides which bucket to put them in.

- Handles collisions internally (buckets + open addressing).

- Resizes automatically when needed.

👉 Writing your own hash function is great for learning DSA, but in production Go code you almost always use map.

Circular Buffers

It is used to wrap indices around when they exceed the buffer size.

Go implementation:

1
nextIndex := (currentIndex + 1) % bufferSize

currentIndex → where you are now.
+1 → move forward.
% bufferSize → wraps back to 0 when you reach the end.

A circular buffer (or ring buffer) is a fixed-size data structure that treats memory as if it were connected end-to-end in a circle. When the index reaches the end of the buffer, it wraps back to the beginning.

This makes it very useful for:

Streaming data (audio, video, logs).
Queues with fixed memory (no growing slices).
Producer–consumer problems (bounded buffer).

🔄 Example Walkthrough

Say bufferSize = 5, indices = 0–4.

If currentIndex = 3:

1
nextIndex = (3 + 1) % 5 = 4

→ move to index 4.

If currentIndex = 4:

1
nextIndex = (4 + 1) % 5 = 0

→ wrap around to index 0.

✅ The % operator ensures the index always stays inside [0 … bufferSize-1].

🛠️ Simple Go Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
package main

import "fmt"

func main() {
bufferSize := 5
buffer := make([]int, bufferSize)

    for i := 0; i < 12; i++ {
        idx := i % bufferSize
        buffer[idx] = i
        fmt.Printf("Write %2d → slot %d | buffer: %v\n", i, idx, buffer)
    }
}

Output:

1
2
3
4
5
6
7
8
Write  0 → slot 0 | buffer: [0 0 0 0 0]
Write  1 → slot 1 | buffer: [0 1 0 0 0]
Write  2 → slot 2 | buffer: [0 1 2 0 0]
Write  3 → slot 3 | buffer: [0 1 2 3 0]
Write  4 → slot 4 | buffer: [0 1 2 3 4]
Write  5 → slot 0 | buffer: [5 1 2 3 4]
Write  6 → slot 1 | buffer: [5 6 2 3 4]
...

👉 Notice how after filling slots 0–4, writing continues at slot 0 again, overwriting old data.

Python implementation:

1
next_index = (current_index + 1) % buffer_size

📌 Use Cases

Log buffers → keep last N entries.
Network packets → stream without resizing memory.
Real-time systems → bounded memory, no GC spikes.

✅ Key Takeaway: Circular buffers use modulus arithmetic to “wrap around” indices. They’re memory-efficient and perfect for streaming and queue-like scenarios where overwriting old data is acceptable.

Key Insights

Modulo is the perfect operator when dealing with:

Repetition (time, days, rotations)
Bounded ranges (array indices, hash maps)
Divisibility checks

Think of % as the wrap-around operator — it keeps numbers within limits.

🧠 Tips for Learning DSA with Go

Practice problems: Use platforms like LeetCode, HackerRank, or Exercism.
Understand time complexity: Know Big-O analysis for every structure and algorithm.
Build mini-projects: Implement your own LRU Cache, Trie, or Priority Queue.

🎯 Final Thoughts

Mastering DSA not only sharpens your coding skills but also prepares you for systems design, performance optimization, and real-world problem-solving.

With Go’s clean syntax and powerful standard library, you’re equipped to tackle DSA challenges efficiently and idiomatically.

🚀 Follow me on norbix.dev for more insights on Go, Python, AI, system design, and engineering wisdom.

🧠 Mastering Data Structures and Algorithms (DSA) with Go and its Python Counterpart

🚀 What is DSA?

📦 Essential Data Structures in Go and its Python Counterpart

🧩 Must-Know Algorithms in Go

🔃 Sort Algorithms

📑 Sorting Algorithms - Cheat Sheet

🔍 Search Algorithms

🔍 Search Algorithms – Cheat Sheet

🌳 Tree Traversal Algorithms

🌳 Tree Traversal Algorithms – Cheat Sheet

➗ The Modulo Operator (%)

What Is Modulo?

When Do We Use Modulo?

Key Insights

🧠 Tips for Learning DSA with Go

🎯 Final Thoughts

🧠 Mastering Data Structures and Algorithms (DSA) with `Go` and its `Python` Counterpart

📦 Essential Data Structures in `Go` and its `Python` Counterpart

🧩 Must-Know Algorithms in `Go`