Loading...

C essentialsData Structures

Data structures: trees & hash tables

20 min lesson

Next
  • 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.
Keep in mind
  • 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!
main.c
#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

FeatureBSTHash table
Average searchO(log n) if balancedO(1) average
Worst searchO(n) if unbalancedO(n) with collisions
Ordered iterationYes, in-orderNo natural order
MemoryPointers per nodeArray of buckets
Use caseSorted data, rangesFast 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 free

Use 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 tree

Use instead

insert in random or balanced order

Sorted 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; // overwrites

Use instead

chain or probe on collision

Two 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.
Previous
Next