Trees and Heaps¶
Trees are recursive by design and heaps are arrays with pointer arithmetic in disguise. Both are so central to the study grind that you’ll have templates memorized after ten problems. This file gives you those templates and the one big surprise: the binary heap is an array, not a tree of pointers, and it’s the single simplest data structure in DSA once you see it.
Binary Trees: The Node and the Templates¶
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
LeetCode ships this exact struct. Get used to it.
The Four Traversals¶
All four fit on one page. Memorize them.
Inorder (left, self, right) — for BSTs, produces sorted order:
void inorder(TreeNode *root, int *out, int *idx) {
if (!root) return;
inorder(root->left, out, idx);
out[(*idx)++] = root->val;
inorder(root->right, out, idx);
}
Preorder (self, left, right) — for tree serialization:
void preorder(TreeNode *root) {
if (!root) return;
/* visit */;
preorder(root->left);
preorder(root->right);
}
Postorder (left, right, self) — for tree deletion, subtree-summing:
void postorder(TreeNode *root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
/* visit */;
}
Level-order / BFS — requires a queue:
void bfs(TreeNode *root) {
if (!root) return;
Queue q = queue_new();
queue_push(&q, root);
while (!queue_empty(&q)) {
TreeNode *n = queue_pop(&q);
/* visit */
if (n->left) queue_push(&q, n->left);
if (n->right) queue_push(&q, n->right);
}
queue_destroy(&q);
}
Your Queue lives in libprep — don’t rewrite it per problem.
Recursion Depth: The Silent Killer¶
A skewed tree (essentially a linked list) has depth N. With 10⁵ nodes and ~1KB of stack per frame, that’s 100 MB of stack — well past the 8 MB default. LeetCode grading machines don’t crash on this often because the test inputs are usually balanced-ish, but on Hard problems (like Serialize and Deserialize Binary Tree with adversarial inputs), you might need to convert to iterative + explicit stack.
// Iterative inorder using a stack (from libprep)
void iter_inorder(TreeNode *root) {
Stack s = stack_new();
TreeNode *curr = root;
while (curr || !stack_empty(&s)) {
while (curr) { stack_push(&s, curr); curr = curr->left; }
curr = stack_pop(&s);
/* visit curr */
curr = curr->right;
}
stack_destroy(&s);
}
Memorize this pattern for at least one traversal; you’ll be graded on it eventually.
BST Operations¶
Binary Search Tree: for every node, left subtree < node < right subtree. Search, insert, delete are all O(h) where h is height (O(log n) for balanced, O(n) for skewed).
Insert (recursive, returns new subtree root):
TreeNode *bst_insert(TreeNode *root, int val) {
if (!root) {
TreeNode *n = malloc(sizeof *n);
*n = (TreeNode){ .val = val };
return n;
}
if (val < root->val) root->left = bst_insert(root->left, val);
else root->right = bst_insert(root->right, val);
return root;
}
Validate BST: not “left < root, right > root” — that’s the trap. Every node in the left subtree must be less than root; every node in the right subtree must be greater. Pass down min/max bounds:
bool is_bst(TreeNode *root, long lo, long hi) {
if (!root) return true;
if (root->val <= lo || root->val >= hi) return false;
return is_bst(root->left, lo, root->val)
&& is_bst(root->right, root->val, hi);
}
// call: is_bst(root, LONG_MIN, LONG_MAX);
Note the long: int bounds don’t work if the tree contains INT_MIN or INT_MAX. This is a classic C-in-studies trap; see 09_c_specific_pitfalls_in_interviews.md.
AVL vs Red-Black: What to Know¶
Self-balancing BSTs come in two families you should be able to name:
AVL trees: balance factor per node is -1/0/1. More rigorously balanced. Faster lookups, slower inserts. Rarely asked in studies.
Red-Black trees: relaxed balance (root-leaf paths within 2x). Slightly less balanced but faster mutations. What
std::map, Linux kernel’srbtree.h, and Java’sTreeMapuse internally.
For studies: know the shape of the problem — “a BST that guarantees O(log n) operations” — and know that Red-Black is the standard implementation. Don’t try to implement either. They’re 200-500 line beasts and no study partner will ask you to code one on a whiteboard. If a problem seems to want one, use a sorted container abstraction (in C: a hash-based multiset if order doesn’t matter, or convert-sort-scan if it does).
Tries¶
A prefix tree for strings, one node per character.
typedef struct TrieNode {
struct TrieNode *children[26]; // for lowercase English
bool is_word;
} TrieNode;
void trie_insert(TrieNode *root, const char *s) {
TrieNode *curr = root;
for (int i = 0; s[i]; i++) {
int c = s[i] - 'a';
if (!curr->children[c]) {
curr->children[c] = calloc(1, sizeof(TrieNode));
}
curr = curr->children[c];
}
curr->is_word = true;
}
Used for: Implement Trie, Word Search II (trie + DFS), Design Add-and-Search-Words, Longest Common Prefix.
Memory footprint: each node is 26 * sizeof(ptr) + bool = 209 bytes. For alphabets larger than 26, use a hashmap of child pointers per node instead of a fixed array.
Binary Heap: The Array-Backed Trick¶
This is the moment C shines. A binary heap is just an array, with the tree structure implicit in the indices:
for node at index i:
parent = (i - 1) / 2
left child = 2 * i + 1
right child = 2 * i + 2
No pointers. No allocations per node. Cache-friendly linear scan.
Min-Heap Operations¶
typedef struct {
int *data;
size_t len, cap;
} MinHeap;
static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
void heap_push(MinHeap *h, int val) {
if (h->len == h->cap) { h->cap *= 2; h->data = realloc(h->data, h->cap * sizeof(int)); }
h->data[h->len++] = val;
// sift up
size_t i = h->len - 1;
while (i > 0) {
size_t p = (i - 1) / 2;
if (h->data[p] <= h->data[i]) break;
swap(&h->data[p], &h->data[i]);
i = p;
}
}
int heap_pop(MinHeap *h) {
int min = h->data[0];
h->data[0] = h->data[--h->len];
// sift down
size_t i = 0;
for (;;) {
size_t l = 2*i + 1, r = 2*i + 2, best = i;
if (l < h->len && h->data[l] < h->data[best]) best = l;
if (r < h->len && h->data[r] < h->data[best]) best = r;
if (best == i) break;
swap(&h->data[i], &h->data[best]);
i = best;
}
return min;
}
That’s the whole heap. ~40 lines. Put it in libprep and never rewrite it. For a max-heap, invert the comparisons. For a heap of structs, replace int with your struct and use a comparator function pointer.
Heapify (Build in O(n))¶
Building a heap from an array by pushing N times is O(n log n). The linear-time build:
void heap_build(MinHeap *h, int *arr, size_t n) {
// copy arr into h->data, set h->len = n
for (ssize_t i = (ssize_t)n / 2 - 1; i >= 0; i--) {
sift_down(h, (size_t)i);
}
}
The intuition: leaf nodes are already valid heaps of size 1. Work up from the last non-leaf, sifting down. Total work is Σ(n/2^k * k) = O(n).
K-th Largest Pattern¶
The defining heap pattern for studies. Given an array, find the k-th largest element:
Approach A: min-heap of size K. For each element, push if heap size < K, else if element > heap.top, pop and push. After processing, heap.top is the k-th largest. O(n log k).
Approach B: max-heap of all N elements, pop K times. O(n + k log n).
Which to use? A when K << N; B otherwise. A is what study partners usually want to see because it introduces the “heap of size K” idiom that shows up in Top K Frequent, Merge K Sorted Lists, Find Median from Data Stream (two heaps trick).
The Two-Heaps Trick (Find Median from Data Stream)¶
Maintain a max-heap of the lower half and a min-heap of the upper half. The median is either the top of one heap or the average of both tops. Balance so their sizes differ by at most 1. Everything is O(log n) per insert, O(1) per median query. Beautiful problem. Solve it.
What Most People Get Wrong About This¶
They learn heaps as trees of pointers, then re-derive the array version each time. It’s the other way around: heap is an array; the tree is a mental picture, not a data structure. Once that clicks, half of the medium-difficulty heap problems become trivial and the two-heaps trick stops being scary.
Return to README.md · Next: 06_graphs_bfs_dfs.md