Data Structures & Algorithms

why hand-build these, when the STL has containers

Production code reaches for std::vector, std::map, and std::sort almost always — but understanding what those are actually doing underneath, and being able to build a linked list, a tree, or a graph traversal by hand, is the difference between using the STL and knowing when its performance characteristics don't fit your problem. This is also, frankly, interview territory: these are the structures that come up.

linked list


struct Node {
  int value;
  Node *next = nullptr;
};

class LinkedList {
  Node *head = nullptr;
public:
  void pushFront(int v) {
    Node *n = new Node{v, head};
    head = n;
  }
  ~LinkedList() {                 // without this, every node leaks
    while (head) {
      Node *next = head->next;
      delete head;
      head = next;
    }
  }
};

A hand-rolled linked list is exactly the case smart pointers were built for — replacing the raw Node* with std::unique_ptr<Node> and chaining ownership node-to-node deletes the entire list automatically when the head goes out of scope, no destructor loop required.

tree traversal

Depth-first traversal of a binary tree comes in three orders, distinguished by when the root is visited relative to its children:

Order	Sequence	Typical use
Preorder	Root → Left → Right	copying/serializing a tree — root written before its subtrees
Inorder	Left → Root → Right	on a binary search tree specifically, this visits keys in sorted order
Postorder	Left → Right → Root	deleting a tree — children freed before their parent


struct TreeNode { int val; TreeNode *left = nullptr, *right = nullptr; };

void inorder(TreeNode *node) {
  if (!node) return;
  inorder(node->left);
  std::cout << node->val << " ";
  inorder(node->right);
}

Level-order traversal (breadth-first) visits the tree one depth level at a time instead — it needs a queue rather than recursion, which is really the same algorithm as BFS on a graph below, specialized to a tree's parent/child edges.

graph traversal: BFS vs. DFS

Both visit every reachable node exactly once, using a visited array to avoid infinite loops on cyclic graphs. They differ in exploration order and in which data structure drives that order: BFS explores level by level using a queue (FIFO); DFS dives as deep as possible before backtracking, using either recursion (the call stack) or an explicit stack.


void BFS(int start, const std::vector<std::list<int>> &adj) {
  std::vector<bool> visited(adj.size(), false);
  std::queue<int> q;
  visited[start] = true;
  q.push(start);
  while (!q.empty()) {
    int v = q.front(); q.pop();
    std::cout << v << " ";
    for (int neighbor : adj[v]) {
      if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); }
    }
  }
}

void DFS(int v, const std::vector<std::list<int>> &adj, std::vector<bool> &visited) {
  visited[v] = true;
  std::cout << v << " ";
  for (int neighbor : adj[v]) {
    if (!visited[neighbor]) DFS(neighbor, adj, visited);   // recursion = implicit stack
  }
}

Both run in O(V + E) time (every vertex and every edge is examined once) and O(V) space for the visited array. Full runnable version, adjacency-list graph plus both traversals side by side: TopNotchNote/cpp/dsa_graph_bfs_dfs.cpp

binary search


int binarySearch(const std::vector<int> &sorted, int target) {
  int lo = 0, hi = (int)sorted.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;    // avoids (lo+hi) overflow on very large indices
    if (sorted[mid] == target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

O(log n) — requires the input already sorted. std::lower_bound/ std::upper_bound (see STL Algorithms & Iterators) do the same search via the standard library rather than by hand.

merge sort


void merge(std::vector<int> &v, int lo, int mid, int hi) {
  std::vector<int> tmp(v.begin() + lo, v.begin() + hi + 1);
  int i = lo, j = mid + 1, k = 0;
  while (i <= mid && j <= hi)
    v[lo + k++] = (tmp[i - lo] <= tmp[j - lo]) ? tmp[i++ - lo] : tmp[j++ - lo];
  while (i <= mid) v[lo + k++] = tmp[i++ - lo];
  while (j <= hi)  v[lo + k++] = tmp[j++ - lo];
}

void mergeSort(std::vector<int> &v, int lo, int hi) {
  if (lo >= hi) return;
  int mid = lo + (hi - lo) / 2;
  mergeSort(v, lo, mid);
  mergeSort(v, mid + 1, hi);
  merge(v, lo, mid, hi);
}

Guaranteed O(n log n) in every case (unlike quicksort's O(n²) worst case), at the cost of O(n) auxiliary space for the merge step — the classic time/space tradeoff between the two.

union-find (disjoint set)

Tracks a collection of disjoint sets, answering "are these two elements in the same set" and "merge these two sets" efficiently. Two competing naive implementations, each with one fast operation and one slow one:

Implementation	find()	union()
Quick find (each element stores its set's root directly)	O(1)	O(n) — updating every element in a merged set
Quick union (each element stores its immediate parent)	O(n) worst case — may walk a long chain to the root	O(1)


class QuickUnion {
  std::vector<int> parent;
public:
  QuickUnion(int n) : parent(n) { std::iota(parent.begin(), parent.end(), 0); }  // each element starts as its own root

  int find(int p) {
    while (parent[p] != p) p = parent[p];
    return p;
  }
  void unite(int p, int q) {
    int rootP = find(p), rootQ = find(q);
    if (rootP != rootQ) parent[rootQ] = rootP;
  }
};

Two optimizations fix quick union's worst case, and are near-mandatory together in practice: union by rank always attaches the shorter tree under the taller one's root (keeping trees flatter as they merge), and path compression repoints every node visited during a find directly to the root it discovers, flattening future lookups. Combined, both operations become effectively O(α(n)) — the inverse Ackermann function, so close to constant time that it's treated as O(1) in practice.

topological sort

Orders the vertices of a directed acyclic graph (DAG) so that every edge points from an earlier vertex to a later one — the classic use case is scheduling tasks with dependencies (a build system, a course prerequisite chain). Kahn's algorithm computes it via BFS: repeatedly remove a vertex with no remaining incoming edges (in-degree zero), and decrement its neighbors' in-degrees as you go.


std::vector<int> topoSort(int n, const std::vector<std::list<int>> &adj) {
  std::vector<int> inDegree(n, 0);
  for (int v = 0; v < n; v++)
    for (int neighbor : adj[v]) inDegree[neighbor]++;

  std::queue<int> ready;
  for (int v = 0; v < n; v++) if (inDegree[v] == 0) ready.push(v);

  std::vector<int> order;
  while (!ready.empty()) {
    int v = ready.front(); ready.pop();
    order.push_back(v);
    for (int neighbor : adj[v]) if (--inDegree[neighbor] == 0) ready.push(neighbor);
  }
  return order;   // if order.size() < n, the graph has a cycle — no valid topological order exists
}

where to go from here

STL Containers — the production-ready versions of the structures built by hand here.
STL Algorithms & Iterators — std::sort, std::lower_bound, and friends.
Smart Pointers — owning linked-list/tree nodes without a manual destructor loop.

reference

cppreference — std::lower_bound
cp-algorithms.com — disjoint set union