Data structures: trees & hash tables
20 min lesson
- A tree is a structure where each node has zero or more children, and a hash table is a structure that maps keys to values using a hash function for fast lookup.
- They matter because both give fast search, insert and delete on large data, which arrays and linked lists cannot do well.
- Think of a tree as a family tree or a folder structure: each node has children, and you follow branches to find what you want. Think of a hash table as a set of labeled mail slots: the key tells you which slot to check.
- A binary search tree (BST) has at most two children per node, with smaller values on the left and larger on the right, so search can skip half the tree at each step.
- A hash table stores key-value pairs in an array of buckets; a hash function turns a key into a bucket index, and collisions are handled by chaining or open addressing.
- The computer follows pointers down a tree for search, or computes a hash and jumps to a bucket for lookup, giving average O(log n) for trees and O(1) for hash tables.
- The syntax for a tree node is: struct Node { int key; struct Node *left; struct Node *right; }; and for a hash table: an array of buckets, each a small list.
- A realistic use: a BST for an ordered set of records, and a hash table for a phone book or a symbol table in a compiler.
- A surprising detail: a badly balanced BST degenerates into a linked list with O(n) search, and a bad hash function causes many collisions and slow lookups.
- The example program builds a small binary search tree by inserting values, searches for one value, and prints the tree in order.
- Use a tree when you need sorted order and range queries; use a hash table for fast key lookups.
- Keep BSTs balanced, or search time degrades to O(n).
- Choose a good hash function and handle collisions carefully.
- Both structures are built from pointers and dynamic memory, so free them when done.
- You are now working with real data structures. Fantastic progress!
#include <stdio.h>
#include <stdlib.h>
// A binary search tree node
struct Node {
int key;
struct Node *left;
struct Node *right;
};
// Insert a key into the tree, keeping BST order
struct Node *insert(struct Node *root, int key) {
// If the tree is empty here, create a new leaf
if (root == NULL) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) return NULL;
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
// Smaller keys go left, larger keys go right
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
// Equal keys are ignored here
return root;
}
// Search for a key; return 1 if found, 0 otherwise
int search(struct Node *root, int key) {
// Reached a leaf without finding the key
if (root == NULL) return 0;
// Found the key
if (key == root->key) return 1;
// Go left or right depending on the key
if (key < root->key) return search(root->left, key);
return search(root->right, key);
}
// In-order traversal prints keys in sorted order
void printInOrder(struct Node *root) {
if (root == NULL) return;
printInOrder(root->left);
printf("%d ", root->key);
printInOrder(root->right);
}
// Free every node in the tree
void freeTree(struct Node *root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main(void) {
// Build a small tree
struct Node *root = NULL;
int keys[] = {50, 30, 70, 20, 40, 60, 80};
for (int i = 0; i < 7; i++) {
root = insert(root, keys[i]);
}
// Print keys in sorted order
printf("In order: ");
printInOrder(root);
printf("\n");
// Search for two keys
printf("Find 40: %d\n", search(root, 40));
printf("Find 90: %d\n", search(root, 90));
// Free the whole tree
freeTree(root);
return 0;
}What happens: In order: 20 30 40 50 60 70 80 Find 40: 1 Find 90: 0
Breaking it down
Tree node
struct Node { int key; struct Node *left, *right; };Each node holds a key and pointers to two children. The left and right pointers form the branches.
Insert
if (key < root->key) root->left = insert(root->left, key);Follows the BST rule: smaller keys go left, larger keys go right, until an empty spot is found.
Search
if (key == root->key) return 1;Compares the key at each node and moves left or right. Each step halves the remaining work in a balanced tree.
In-order print
printInOrder(root->left); printf(...); printInOrder(root->right);Visits left subtree, then the node, then the right subtree. This prints keys in sorted order.
Free tree
freeTree(root->left); freeTree(root->right); free(root);Recursively frees children before the parent. Freeing the parent first would lose the pointers to the children.
Tree vs hash table
| Feature | BST | Hash table |
|---|---|---|
| Average search | O(log n) if balanced | O(1) average |
| Worst search | O(n) if unbalanced | O(n) with collisions |
| Ordered iteration | Yes, in-order | No natural order |
| Memory | Pointers per node | Array of buckets |
| Use case | Sorted data, ranges | Fast key lookups |
A helpful analogy
A tree is like a family tree or a folder structure: each node has children, and you follow the branches that match your search. A hash table is like a set of labeled mail slots: the key tells you exactly which slot to check, so you go straight there instead of looking through every slot.
Nesting rules
- 1.In a BST, every left child must be smaller and every right child larger than its parent.
- 2.Free a tree by freeing children before the parent, or you lose their pointers.
- 3.Hash tables must handle collisions; chaining with a small list per bucket is the simplest.
- 4.Keep BSTs balanced for O(log n) search; unbalanced trees degrade to O(n).
Common mistakes
Freeing the parent before the children
Avoid
free(root);
freeTree(root->left); // use after freeUse instead
freeTree(root->left);
freeTree(root->right);
free(root);Freeing the parent first loses the pointers to the children, leaking them. Free children first.
Inserting into a BST in sorted order
Avoid
insert(1,2,3,4,5) // list-shaped treeUse instead
insert in random or balanced orderSorted insertion creates a chain, making search O(n). Use a balanced tree or shuffle the input.
Ignoring collisions in a hash table
Avoid
table[h] = value; // overwritesUse instead
chain or probe on collisionTwo keys can hash to the same bucket. Without collision handling, one value overwrites the other.
Quick tips
- •Draw small trees on paper to check insert and search logic.
- •Print the tree in order to confirm the BST property after each insert.
- •Use random insertion order to avoid degenerate trees in practice.
- •For hash tables, choose a prime bucket count and a simple hash like key % size.
- •Free every node before the program ends to keep Valgrind happy.