What You'll Learn
- Binary search trees with smart pointers
- Heaps and priority queues
- Graphs with BFS and DFS
- When to use each data structure
Data Structures in C++
Beyond vectors and maps, C++ lets you build powerful data structures from scratch. This lesson covers binary search trees (BSTs), heaps/priority queues, and graphs — the three structures that appear in nearly every technical interview and production system.
Binary Search Trees
A BST stores values such that left children are smaller and right children are larger. This enables O(log n) search, insert, and delete on average. In-order traversal yields sorted output. Using unique_ptr for children ensures automatic memory cleanup.
Common Mistake: Unbalanced BSTs degrade to O(n) — inserting sorted data creates a linked list. Use std::set (red-black tree) for guaranteed O(log n) in production.
Binary Search Tree
Insert, search, and traverse a BST with smart pointers
#include <iostream>
#include <memory>
using namespace std;
// Binary Search Tree — O(log n) average insert/search
struct Node {
int value;
unique_ptr<Node> left, right;
Node(int v) : value(v) {}
};
class BST {
unique_ptr<Node> root;
void insert(unique_ptr<Node>& node, int val) {
if (!node) { node = make_unique<Node>(val); return; }
if (val < node->value) insert(node->left, val);
else if (val > node->value) insert(node->right, val);
}
bool s
...Heaps & Priority Queues
A heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children. std::priority_queue provides a ready-made max-heap; use greater<> for min-heap. Heaps power task schedulers, Dijkstra's algorithm, and merge-k-sorted-lists.
Pro Tip: For top-K problems, use a min-heap of size K. Push each element; if size exceeds K, pop the minimum. At the end, the heap contains the K largest elements.
Heaps & Priority Queues
Min-heap operations and a task scheduler
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
cout << "=== Min-Heap with priority_queue ===" << endl;
// Default priority_queue is max-heap
// Use greater<> for min-heap
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int v : {42, 17, 93, 5, 68, 31, 85}) {
minHeap.push(v);
cout << "Push " << v << " → top: " << minHeap.top() << endl;
}
cout << "\nPop order (min first): ";
...Graphs — BFS & DFS
Graphs represent connections: social networks, road maps, dependency trees. An adjacency list is the most common representation — each node stores a list of its neighbors. BFS finds shortest paths (unweighted); DFS explores all reachable nodes.
Graphs
Build a weighted graph with BFS and DFS traversal
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// Adjacency list graph
class Graph {
unordered_map<string, vector<pair<string, int>>> adj;
public:
void addEdge(const string& from, const string& to, int weight = 1) {
adj[from].push_back({to, weight});
adj[to].push_back({from, weight}); // undirected
}
// Breadth-First Search — shortest path (unweighted)
void bfs(const string& star
...Quick Reference
| Structure | Insert | Search | Use Case |
|---|---|---|---|
| BST | O(log n) | O(log n) | Sorted data, range queries |
| Heap | O(log n) | O(1) top | Priority scheduling, top-K |
| Graph (adj list) | O(1) | O(V+E) | Networks, pathfinding |
| Trie | O(len) | O(len) | Prefix search, autocomplete |
Lesson Complete!
You can now implement BSTs, heaps, and graphs in C++ — the foundation of algorithms and system design.
Sign up for free to track which lessons you've completed and get learning reminders.