Bytebook Compiler

Bytebook · CSE 102

Data Structures

Build every classic data structure in C — linked lists, stacks, queues, trees, heaps, graphs and hash tables — and learn exactly when to use each one.

Back to lessons

Chapter 1 · Foundations

Introduction to Data Structures

What a data structure is, abstract data types, linear vs non-linear structures, and why choosing well matters more than coding fast.

A data structure is a way of organising data in memory so that the operations you need — search, insert, delete, find the smallest — are fast. The same million phone numbers can be stored in an array, a linked list, a tree or a hash table; each choice makes some operations quick and others slow.

Bad programmers worry about the code. Good programmers worry about data structures and their relationships. — Linus Torvalds

Why it matters

Imagine looking up a contact among 1,000,000 numbers:

Structure Steps to find one number (worst case)
Unsorted array, linear search 1,000,000
Sorted array, binary search about 20
Hash table about 1

Same data, same computer — a 1,000,000× difference, purely from how the data is organised.

Abstract data types

An abstract data type (ADT) describes what operations a structure supports, not how they are implemented. A data structure is a concrete implementation of an ADT.

ADT Operations Common implementations
List insert, delete, get(i), search array, linked list
Stack push, pop, peek array, linked list
Queue enqueue, dequeue, front circular array, linked list
Priority queue insert, extract-min/max binary heap
Map / dictionary put(key, value), get(key) hash table, balanced BST
Set add, remove, contains hash table, BST

Think of an ADT as a remote control's buttons, and the data structure as the electronics inside.

Classifying data structures

intfloatcharPrimitiveArrayListStackQueueLinearTreeGraphNon-linearNon-primitiveData Structures
The classification examiners expect. Linear structures arrange elements in a sequence; non-linear ones branch.
  • Linear: elements form a sequence, each with at most one predecessor and successor — arrays, linked lists, stacks, queues.
  • Non-linear: an element can connect to many others — trees (hierarchies) and graphs (networks).
  • Static: size fixed at compile time (a C array).
  • Dynamic: grows and shrinks at run time (a linked list built with malloc).

The operations we measure

Every structure in this course is judged by the cost of a handful of operations:

  1. Traversal — visit every element once.
  2. Search — find an element with a given key.
  3. Insertion — add an element.
  4. Deletion — remove an element.
  5. Sorting and merging — for collections of data.

The next lesson gives you the language for comparing those costs: Big-O notation.

A first taste: the same job, two structures

Both programs below store marks and answer "is 72 in the list?". The array keeps data in one block; the linked list chains separate nodes together with pointers. You will build both properly in this course.

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

int main(void) {
    int arr[] = {55, 72, 81, 64};
    for (int i = 0; i < 4; i++)
        if (arr[i] == 72) printf("array: found 72 at index %d\n", i);

    Node *head = NULL;                       // build list 64 -> 81 -> 72 -> 55 by inserting at the front
    for (int i = 0; i < 4; i++) {
        Node *n = malloc(sizeof(Node));
        n->data = arr[i];
        n->next = head;
        head = n;
    }
    int pos = 0;
    for (Node *p = head; p; p = p->next, pos++)
        if (p->data == 72) printf("list:  found 72 at node %d\n", pos);
    while (head) { Node *t = head; head = head->next; free(t); }
    return 0;
}
Output
array: found 72 at index 1
list:  found 72 at node 2
Try it Yourself

Chapter 2 · Foundations

Time & Space Complexity

Count steps instead of seconds: Big-O notation, the common growth rates, analysing loops, and best, average and worst cases.

How do you compare two algorithms? Timing them with a stopwatch depends on the computer, the compiler and the input. Instead we count how the number of basic steps grows with the input size n. That growth rate is the algorithm's time complexity.

Big-O notation

O(f(n)) describes an upper bound on growth, ignoring constants and smaller terms:

  • 3n² + 5n + 100 → O(n²) (n² dominates for large n)
  • 7n + 20 → O(n)
  • 500 → O(1)

We drop constants because we care about scaling: does doubling the input double the work, quadruple it, or barely change it?

The growth rates you must know

Big-O Name Example n = 1,000
O(1) constant array index, hash lookup 1
O(log n) logarithmic binary search ~10
O(n) linear linear search, traversal 1,000
O(n log n) linearithmic merge sort, heap sort ~10,000
O(n²) quadratic bubble sort, nested loops 1,000,000
O(2ⁿ) exponential naive Fibonacci, all subsets ~10³⁰⁰
O(n!) factorial all permutations unimaginable

Drag the slider to feel the difference:

Analysing code

Count how many times the innermost statement runs.

C
// O(1): no loops depending on n
int first = a[0];

// O(n): one loop over n elements
for (int i = 0; i < n; i++) sum += a[i];

// O(n^2): a loop inside a loop, both over n
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) count++;

// O(log n): i doubles each time, so it reaches n after log2(n) steps
for (int i = 1; i < n; i *= 2) steps++;

// O(n log n): an O(log n) loop inside an O(n) loop
for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j *= 2) work++;

You can check the counting by running it:

C
#include <stdio.h>

int main(void) {
    int sizes[] = {10, 100, 1000};
    for (int s = 0; s < 3; s++) {
        int n = sizes[s];
        long linear = 0, quad = 0, logn = 0, tri = 0;
        for (int i = 0; i < n; i++) linear++;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) quad++;
        for (int i = 1; i < n; i *= 2) logn++;
        for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) tri++;   // still O(n^2): n(n-1)/2
        printf("n=%4d  log:%2ld  linear:%5ld  triangle:%7ld  square:%8ld\n", n, logn, linear, tri, quad);
    }
    return 0;
}
Output
n=  10  log: 4  linear:   10  triangle:     45  square:     100
n= 100  log: 7  linear:  100  triangle:   4950  square:   10000
n=1000  log:10  linear: 1000  triangle: 499500  square: 1000000
Try it Yourself

The "triangle" loop does n(n−1)/2 steps — about half of n², but still O(n²), because constants are dropped.

Rules of thumb

  1. Sequential steps add: O(n) followed by O(n²) is O(n + n²) = O(n²).
  2. Nested loops multiply: an O(n) loop inside an O(n) loop is O(n²).
  3. Drop constants and lower terms: O(2n + 10) = O(n).
  4. Halving or doubling the remaining work each step gives O(log n).
  5. Different inputs keep different letters: looping over n items then m items is O(n + m), not O(n).

Best, average and worst case

The same algorithm can take different time on different inputs of the same size. For linear search on n items:

  • Best case: the key is first — 1 comparison, O(1).
  • Worst case: the key is last or absent — n comparisons, O(n).
  • Average case: about n/2 comparisons — still O(n).

We usually quote the worst case, because it is a guarantee.

Space complexity

Space complexity measures extra memory used as n grows. Reversing an array in place uses O(1) extra space; copying it into a new array uses O(n). A recursive function uses stack space proportional to its maximum recursion depth.

Chapter 3 · Foundations

Arrays as a Data Structure

Arrays from the data-structure point of view: O(1) access, the cost of insertion and deletion by shifting, and when an array is the right choice.

You already know how to use arrays from the C course. Here we look at them as a data structure: what each operation costs.

An array stores elements in contiguous memory. Because every element has the same size, the address of a[i] is simply base + i × size. That makes access O(1) — the computer jumps straight there.

120251312473584_5_6basea[3]
a[3] is at base + 3 × 4 bytes. No searching needed, so indexing is O(1). The _ cells are spare capacity.

Insertion at a position

To insert at index pos, every element from pos onwards must shift one place right to make room. Inserting at the front of n elements moves all n: O(n).

C
#include <stdio.h>

int insertAt(int a[], int n, int cap, int pos, int value) {
    if (n == cap || pos < 0 || pos > n) return n;      // full or invalid position
    for (int i = n; i > pos; i--)                       // shift right, starting from the end
        a[i] = a[i - 1];
    a[pos] = value;
    return n + 1;                                       // new size
}

void print(const int a[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[10] = {12, 25, 31, 47, 58};
    int n = 5;
    n = insertAt(a, n, 10, 2, 99);
    print(a, n);
    n = insertAt(a, n, 10, 0, 7);
    print(a, n);
    n = insertAt(a, n, 10, n, 100);   // at the end: no shifting, O(1)
    print(a, n);
    return 0;
}
Output
12 25 99 31 47 58 
7 12 25 99 31 47 58 
7 12 25 99 31 47 58 100
Try it Yourself

Deletion at a position

Deleting shifts the later elements left to close the gap: also O(n) in the worst case.

C
#include <stdio.h>

int deleteAt(int a[], int n, int pos) {
    if (pos < 0 || pos >= n) return n;
    for (int i = pos; i < n - 1; i++)
        a[i] = a[i + 1];
    return n - 1;
}

int main(void) {
    int a[] = {12, 25, 31, 47, 58};
    int n = 5;
    n = deleteAt(a, n, 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
Output
12 31 47 58
Try it Yourself

Array operation costs

Operation Cost Why
Access a[i] O(1) address arithmetic
Update a[i] = x O(1) address arithmetic
Search (unsorted) O(n) may check every element
Search (sorted) O(log n) binary search
Insert / delete at end O(1) nothing to shift
Insert / delete at front or middle O(n) shifting

Strengths and weaknesses

Use an array when you need fast random access by index, the size is known or changes rarely, and you mostly add or remove at the end.

Avoid an array when you insert and delete in the middle a lot, or the size is completely unpredictable — that is where linked lists shine.

Merging two sorted arrays

A pattern you will reuse in merge sort: walk both arrays with two indexes, always taking the smaller front element. It runs in O(n + m).

C
#include <stdio.h>

int main(void) {
    int a[] = {3, 8, 15, 21}, b[] = {1, 9, 10, 22, 30};
    int n = 4, m = 5, c[9], i = 0, j = 0, k = 0;
    while (i < n && j < m) c[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];
    for (int t = 0; t < k; t++) printf("%d ", c[t]);
    printf("\n");
    return 0;
}
Output
1 3 8 9 10 15 21 22 30
Try it Yourself

Chapter 4 · Linked Lists

Singly Linked List

Nodes joined by pointers: create, traverse, insert at the head, tail or a position, delete, and search — with every operation's cost.

A linked list stores elements in separate nodes scattered around memory. Each node holds its data and a pointer to the next node. The list is reached through a pointer to the first node, called the head; the last node points to NULL.

10203040NULLhead
A singly linked list. Each box is a node: data on the left, the next pointer on the right.

Unlike an array, a linked list can grow one node at a time and insert anywhere without shifting other elements — you only rewire pointers.

The node

C
typedef struct Node {
    int data;
    struct Node *next;     // a pointer to another node of the same type
} Node;

A structure that contains a pointer to its own type is called self-referential.

Try it

Insert and delete nodes and watch the pointers change:

The complete program

Every function receives Node **head (a pointer to the head pointer) when it may need to change which node is first.

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node *newNode(int data) {
    Node *n = malloc(sizeof(Node));
    n->data = data;
    n->next = NULL;
    return n;
}

void insertHead(Node **head, int data) {          // O(1)
    Node *n = newNode(data);
    n->next = *head;
    *head = n;
}

void insertTail(Node **head, int data) {          // O(n): walk to the end
    Node *n = newNode(data);
    if (*head == NULL) { *head = n; return; }
    Node *p = *head;
    while (p->next != NULL) p = p->next;
    p->next = n;
}

void insertAt(Node **head, int pos, int data) {   // pos 0 = new head
    if (pos == 0) { insertHead(head, data); return; }
    Node *p = *head;
    for (int i = 0; p != NULL && i < pos - 1; i++) p = p->next;
    if (p == NULL) { printf("position %d out of range\n", pos); return; }
    Node *n = newNode(data);
    n->next = p->next;                            // 1. new node points to the rest
    p->next = n;                                  // 2. previous node points to new node
}

void deleteValue(Node **head, int key) {
    Node *p = *head, *prev = NULL;
    while (p != NULL && p->data != key) { prev = p; p = p->next; }
    if (p == NULL) { printf("%d not found\n", key); return; }
    if (prev == NULL) *head = p->next;            // deleting the head
    else prev->next = p->next;                    // bypass the node
    free(p);
}

int search(Node *head, int key) {
    for (int i = 0; head != NULL; head = head->next, i++)
        if (head->data == key) return i;
    return -1;
}

void print(Node *head) {
    for (; head != NULL; head = head->next) printf("%d -> ", head->data);
    printf("NULL\n");
}

void freeList(Node **head) {
    while (*head) { Node *t = *head; *head = t->next; free(t); }
}

int main(void) {
    Node *head = NULL;
    insertTail(&head, 20);
    insertTail(&head, 30);
    insertHead(&head, 10);
    print(head);
    insertAt(&head, 2, 25);
    print(head);
    deleteValue(&head, 10);
    print(head);
    deleteValue(&head, 99);
    printf("30 is at position %d\n", search(head, 30));
    freeList(&head);
    print(head);
    return 0;
}
Output
10 -> 20 -> 30 -> NULL
10 -> 20 -> 25 -> 30 -> NULL
20 -> 25 -> 30 -> NULL
99 not found
30 is at position 2
NULL
Try it Yourself

Inserting in the middle, step by step

To insert 25 after node 20:

102030NULLhead
Before: p points at 20.
  1. Create the new node: n->data = 25.
  2. Point it at the rest of the list: n->next = p->next; (25 → 30).
  3. Point 20 at it: p->next = n; (20 → 25).
10202530NULLhead
After: only two pointers changed. No other node moved.

Deleting a node

Find the node and the one before it, make the previous node skip over it, then free it. Deleting the head is a special case: move head forward.

Costs: array vs linked list

Operation Array Singly linked list
Access the i-th element O(1) O(n)
Insert / delete at the front O(n) O(1)
Insert / delete at the end O(1) O(n), or O(1) with a tail pointer
Insert / delete after a known node O(n) O(1)
Search O(n) O(n)
Extra memory none one pointer per node
Memory layout contiguous, cache-friendly scattered

Chapter 5 · Linked Lists

Linked List Problems

The classic interview and exam problems: reverse a list, find the middle, detect a cycle with Floyd's algorithm, merge two sorted lists and remove duplicates.

These problems appear constantly in CSE 102 exams and placement interviews. Each uses a small trick with pointers. All of them use this node type and helper:

C
typedef struct Node { int data; struct Node *next; } Node;

Reverse a linked list

Walk the list once, turning each next pointer around. Keep three pointers: prev, cur and next.

1234NULLhead
Before: 1 → 2 → 3 → 4 → NULL
C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node *build(const int *a, int n) {
    Node *head = NULL, **tail = &head;
    for (int i = 0; i < n; i++) {
        *tail = malloc(sizeof(Node));
        (*tail)->data = a[i];
        (*tail)->next = NULL;
        tail = &(*tail)->next;
    }
    return head;
}
void print(const Node *h) { for (; h; h = h->next) printf("%d ", h->data); printf("\n"); }

Node *reverse(Node *head) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;   // 1. remember the rest
        cur->next = prev;         // 2. turn this pointer around
        prev = cur;               // 3. step forward
        cur = next;
    }
    return prev;                  // prev is the new head
}

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    Node *head = build(a, 5);
    print(head);
    head = reverse(head);
    print(head);
    return 0;
}
Output
1 2 3 4 5 
5 4 3 2 1
Try it Yourself

It runs in O(n) time and O(1) extra space. The recursive version is shorter but uses O(n) stack space:

C
Node *reverseRec(Node *head) {
    if (head == NULL || head->next == NULL) return head;
    Node *rest = reverseRec(head->next);
    head->next->next = head;      // the node after head now points back
    head->next = NULL;
    return rest;
}

Find the middle: slow and fast pointers

Move slow one step and fast two steps at a time. When fast reaches the end, slow is in the middle — one pass, no counting.

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node *push(Node *head, int v) { Node *n = malloc(sizeof(Node)); n->data = v; n->next = head; return n; }

int middle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->data;
}

int main(void) {
    Node *odd = NULL, *even = NULL;
    for (int v = 5; v >= 1; v--) odd = push(odd, v);    // 1 2 3 4 5
    for (int v = 6; v >= 1; v--) even = push(even, v);  // 1 2 3 4 5 6
    printf("middle of 1..5 = %d\n", middle(odd));
    printf("middle of 1..6 = %d\n", middle(even));     // second of the two middles
    return 0;
}
Output
middle of 1..5 = 3
middle of 1..6 = 4
Try it Yourself

Detect a cycle: Floyd's tortoise and hare

If a bug makes some node point back to an earlier one, traversal loops forever. Floyd's algorithm uses the same slow/fast idea: in a cycle, the fast pointer eventually laps the slow one and they meet.

12345head
A list whose last node points back to the first. slow and fast must meet inside the loop.
C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

int hasCycle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

int main(void) {
    Node n[5];
    for (int i = 0; i < 5; i++) { n[i].data = i + 1; n[i].next = (i < 4) ? &n[i + 1] : NULL; }
    printf("straight list has cycle? %s\n", hasCycle(&n[0]) ? "yes" : "no");
    n[4].next = &n[1];                     // 5 -> 2 creates a loop
    printf("after 5 -> 2, has cycle? %s\n", hasCycle(&n[0]) ? "yes" : "no");
    return 0;
}
Output
straight list has cycle? no
after 5 -> 2, has cycle? yes
Try it Yourself

Time O(n), space O(1). (A simpler approach stores visited nodes in a hash set, but that costs O(n) memory.)

Merge two sorted lists

Repeatedly take the smaller head. A dummy node avoids special-casing the first element:

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node *fromArray(const int *a, int n) {
    Node *head = NULL;
    for (int i = n - 1; i >= 0; i--) { Node *x = malloc(sizeof(Node)); x->data = a[i]; x->next = head; head = x; }
    return head;
}
void print(const Node *h) { for (; h; h = h->next) printf("%d ", h->data); printf("\n"); }

Node *merge(Node *a, Node *b) {
    Node dummy = {0, NULL}, *tail = &dummy;
    while (a && b) {
        if (a->data <= b->data) { tail->next = a; a = a->next; }
        else                    { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;          // attach whatever is left
    return dummy.next;
}

int main(void) {
    int x[] = {2, 7, 9, 15}, y[] = {1, 3, 8, 20, 21};
    print(merge(fromArray(x, 4), fromArray(y, 5)));
    return 0;
}
Output
1 2 3 7 8 9 15 20 21
Try it Yourself

Remove duplicates from a sorted list

In a sorted list, duplicates sit next to each other, so one pass suffices:

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

int main(void) {
    int a[] = {1, 1, 2, 3, 3, 3, 4, 5, 5};
    Node *head = NULL;
    for (int i = 8; i >= 0; i--) { Node *x = malloc(sizeof(Node)); x->data = a[i]; x->next = head; head = x; }

    for (Node *p = head; p && p->next; ) {
        if (p->data == p->next->data) {
            Node *dup = p->next;
            p->next = dup->next;
            free(dup);
        } else p = p->next;
    }
    for (Node *p = head; p; p = p->next) printf("%d ", p->data);
    printf("\n");
    return 0;
}
Output
1 2 3 4 5
Try it Yourself

Chapter 6 · Linked Lists

Doubly & Circular Linked Lists

Lists that go both ways or loop around: node structure, insertion and deletion in a doubly linked list, circular lists, and when to use each.

Doubly linked list

Each node in a doubly linked list has two pointers: prev and next. You can walk in both directions, and you can delete a node when you only have a pointer to it.

10203040headtail
A doubly linked list. Slashes show NULL: the first node's prev and the last node's next.
C
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prev, *next;
} DNode;

DNode *head = NULL, *tail = NULL;

void pushBack(int v) {                    // O(1) with a tail pointer
    DNode *n = malloc(sizeof(DNode));
    n->data = v; n->next = NULL; n->prev = tail;
    if (tail) tail->next = n; else head = n;
    tail = n;
}

void pushFront(int v) {
    DNode *n = malloc(sizeof(DNode));
    n->data = v; n->prev = NULL; n->next = head;
    if (head) head->prev = n; else tail = n;
    head = n;
}

void removeNode(DNode *n) {               // O(1): no need to search for the previous node
    if (n->prev) n->prev->next = n->next; else head = n->next;
    if (n->next) n->next->prev = n->prev; else tail = n->prev;
    free(n);
}

void printForward(void)  { for (DNode *p = head; p; p = p->next) printf("%d ", p->data); printf("\n"); }
void printBackward(void) { for (DNode *p = tail; p; p = p->prev) printf("%d ", p->data); printf("\n"); }

int main(void) {
    pushBack(20); pushBack(30); pushBack(40); pushFront(10);
    printf("forward:  "); printForward();
    printf("backward: "); printBackward();
    removeNode(head->next);               // remove 20 using just its pointer
    printf("after removing 20: "); printForward();
    removeNode(tail);
    printf("after removing tail: "); printForward();
    return 0;
}
Output
forward:  10 20 30 40 
backward: 40 30 20 10 
after removing 20: 10 30 40 
after removing tail: 10 30
Try it Yourself

When inserting in the middle of a doubly linked list, four pointers change: the new node's prev and next, the previous node's next and the following node's prev.

Circular linked list

In a circular list, the last node points back to the first instead of NULL. There is no natural end, so traversal stops when you return to the starting node. It is often accessed through a pointer to the last node, because last->next is the first node — giving O(1) insertion at both ends.

10203040head
A circular singly linked list. The last node's next points back to the first.
C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node *insertEnd(Node *last, int v) {          // returns the new last node
    Node *n = malloc(sizeof(Node));
    n->data = v;
    if (last == NULL) { n->next = n; return n; }   // one node points to itself
    n->next = last->next;                     // new node points to the first
    last->next = n;
    return n;
}

void print(Node *last) {
    if (!last) return;
    Node *p = last->next;                     // start at the first node
    do { printf("%d ", p->data); p = p->next; } while (p != last->next);
    printf("(back to %d)\n", last->next->data);
}

int main(void) {
    Node *last = NULL;
    for (int v = 10; v <= 40; v += 10) last = insertEnd(last, v);
    print(last);

    // Josephus-style round: remove every 2nd person until one remains
    Node *p = last;
    while (p->next != p) {
        p = p->next;                  // this person survives the round
        Node *out = p->next;          // the next one is removed
        p->next = out->next;
        printf("removed %d\n", out->data);
        free(out);
    }
    printf("survivor: %d\n", p->data);
    return 0;
}
Output
10 20 30 40 (back to 10)
removed 20
removed 40
removed 30
survivor: 10
Try it Yourself

Which list should you use?

Singly Doubly Circular
Pointers per node 1 2 1 (or 2 if doubly circular)
Traverse backwards no yes no
Delete a node given only its pointer no (needs previous) O(1) no
Memory least most least
Natural use stacks, simple lists browser history, LRU caches, text editors round-robin, repeating playlists

Chapter 7 · Stacks & Queues

Stack

Last in, first out: push, pop and peek, overflow and underflow, and two implementations — with an array and with a linked list.

A stack is a collection where you can only add or remove at one end, called the top. The last item pushed is the first one popped: LIFO (Last In, First Out). Think of a pile of plates, the browser Back button, or Undo in a text editor.

10203040topstack
Items are pushed and popped at the top. 40 was pushed last, so it will be popped first.

Operations

Operation Meaning Cost
push(x) put x on top O(1)
pop() remove and return the top item O(1)
peek() / top() look at the top item without removing it O(1)
isEmpty() is the stack empty? O(1)
isFull() (array version) is it at capacity? O(1)

Pushing onto a full array stack is overflow; popping from an empty stack is underflow.

Try it

Array implementation

Keep an array and an index top of the current top element. An empty stack has top = -1.

C
#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

int isEmpty(void) { return top == -1; }
int isFull(void)  { return top == MAX - 1; }

void push(int x) {
    if (isFull()) { printf("Overflow: cannot push %d\n", x); return; }
    stack[++top] = x;
    printf("pushed %d\n", x);
}

int pop(void) {
    if (isEmpty()) { printf("Underflow\n"); return -1; }
    return stack[top--];
}

int peek(void) { return isEmpty() ? -1 : stack[top]; }

int main(void) {
    for (int i = 1; i <= 6; i++) push(i * 10);    // the 6th push overflows
    printf("top is %d\n", peek());
    printf("popped %d\n", pop());
    printf("popped %d\n", pop());
    printf("top is now %d\n", peek());
    return 0;
}
Output
pushed 10
pushed 20
pushed 30
pushed 40
pushed 50
Overflow: cannot push 60
top is 50
popped 50
popped 40
top is now 30
Try it Yourself

Linked-list implementation

Push and pop at the head of a linked list — both O(1) — and the stack never overflows (until memory runs out):

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;
Node *top = NULL;

void push(int x) {
    Node *n = malloc(sizeof(Node));
    n->data = x;
    n->next = top;
    top = n;
}

int pop(void) {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    Node *t = top;
    int x = t->data;
    top = t->next;
    free(t);
    return x;
}

int main(void) {
    const char *word = "STACK";
    for (int i = 0; word[i]; i++) push(word[i]);
    printf("Reversed: ");
    while (top != NULL) printf("%c", pop());     // LIFO reverses the order
    printf("\n");
    pop();
    return 0;
}
Output
Reversed: KCATS
Underflow
Try it Yourself

Array vs linked-list stack

Array Linked list
Size fixed (overflow possible) grows as needed
Memory per item just the data data + pointer
Speed very fast, cache-friendly malloc per push

Where stacks are used

  • Function calls — the call stack stores each function's local variables and return address.
  • Undo/redo and the browser Back button.
  • Expression evaluation and bracket matching — next lesson.
  • Depth-first search and backtracking (mazes, Sudoku).
  • Reversing anything: strings, lists, the digits of a number.

Chapter 8 · Stacks & Queues

Stack Applications

Balanced brackets, infix to postfix conversion and postfix evaluation — the three stack algorithms every CSE 102 exam asks you to trace.

1. Balanced brackets

Every opening bracket must be closed by the matching bracket in the right order. Push each opener; on each closer, pop and check it matches.

C
#include <stdio.h>

int isBalanced(const char *s) {
    char st[100];
    int top = -1;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') st[++top] = c;
        else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return 0;                       // closer with nothing open
            char o = st[top--];
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return 0;
        }
    }
    return top == -1;                                      // anything left open?
}

int main(void) {
    const char *tests[] = {"{[a+b]*(c-d)}", "([)]", "((x)", "a[i] = (b + c) * {d}"};
    for (int i = 0; i < 4; i++)
        printf("%-22s %s\n", tests[i], isBalanced(tests[i]) ? "balanced" : "NOT balanced");
    return 0;
}
Output
{[a+b]*(c-d)}          balanced
([)]                   NOT balanced
((x)                   NOT balanced
a[i] = (b + c) * {d}   balanced
Try it Yourself

Infix, prefix and postfix

Notation Operator position A + B * C Needs brackets?
Infix between operands A + B * C yes, plus precedence rules
Prefix (Polish) before operands + A * B C no
Postfix (Reverse Polish) after operands A B C * + no

Computers prefer postfix: it can be evaluated left to right with one stack and no precedence rules.

2. Infix to postfix (shunting-yard)

Scan the infix expression left to right:

  1. Operand → write it to the output.
  2. ( → push it.
  3. ) → pop to the output until the matching (; discard both brackets.
  4. Operator → while the stack top is an operator of higher precedence, or equal precedence and left-associative, pop it to the output. Then push the new operator.
  5. At the end, pop everything left to the output.

Precedence: ^ (highest, right-associative) > * / > + -.

C
#include <stdio.h>
#include <ctype.h>

int prec(char op) {
    if (op == '^') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

void toPostfix(const char *in, char *out) {
    char st[100];
    int top = -1, k = 0;
    for (int i = 0; in[i]; i++) {
        char c = in[i];
        if (isalnum((unsigned char)c)) out[k++] = c;
        else if (c == '(') st[++top] = c;
        else if (c == ')') {
            while (top >= 0 && st[top] != '(') out[k++] = st[top--];
            top--;                                            // discard '('
        } else if (prec(c)) {
            while (top >= 0 && st[top] != '(' &&
                   (prec(st[top]) > prec(c) || (prec(st[top]) == prec(c) && c != '^')))
                out[k++] = st[top--];
            st[++top] = c;
        }
    }
    while (top >= 0) out[k++] = st[top--];
    out[k] = '\0';
}

int main(void) {
    const char *exprs[] = {"A+B*C", "(A+B)*C", "A+B*C-D/E", "A*(B+C)/D", "A^B^C", "(A-B/C)*(A/K-L)"};
    char post[100];
    for (int i = 0; i < 6; i++) {
        toPostfix(exprs[i], post);
        printf("%-18s ->  %s\n", exprs[i], post);
    }
    return 0;
}
Output
A+B*C              ->  ABC*+
(A+B)*C            ->  AB+C*
A+B*C-D/E          ->  ABC*+DE/-
A*(B+C)/D          ->  ABC+*D/
A^B^C              ->  ABC^^
(A-B/C)*(A/K-L)    ->  ABC/-AK/L-*
Try it Yourself

Tracing A+B*C-D/E

Symbol Action Stack Output
A output A
+ push + A
B output + AB
* higher than +, push + * AB
C output + * ABC
- pop * and + (≥ precedence), push - - ABC*+
D output - ABC*+D
/ higher than -, push - / ABC*+D
E output - / ABC*+DE
end pop all ABC*+DE/-

3. Evaluating postfix

Scan left to right. Push numbers. On an operator, pop two values — the first pop is the right operand — apply the operator and push the result.

C
#include <stdio.h>
#include <ctype.h>

int evalPostfix(const char *s) {
    int st[100], top = -1;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == ' ') continue;
        if (isdigit((unsigned char)c)) {
            int num = 0;
            while (isdigit((unsigned char)s[i])) num = num * 10 + (s[i++] - '0');
            i--;
            st[++top] = num;
        } else {
            int b = st[top--], a = st[top--];       // b is popped first: the right operand
            switch (c) {
                case '+': st[++top] = a + b; break;
                case '-': st[++top] = a - b; break;
                case '*': st[++top] = a * b; break;
                case '/': st[++top] = a / b; break;
            }
        }
    }
    return st[top];
}

int main(void) {
    printf("2 3 1 * + 9 -  = %d\n", evalPostfix("2 3 1 * + 9 -"));
    printf("6 2 / 3 -      = %d\n", evalPostfix("6 2 / 3 -"));
    printf("10 2 8 * + 3 - = %d\n", evalPostfix("10 2 8 * + 3 -"));
    return 0;
}
Output
2 3 1 * + 9 -  = -4
6 2 / 3 -      = 0
10 2 8 * + 3 - = 23
Try it Yourself

Trace of 2 3 1 * + 9 -: push 2, 3, 1 → * pops 1 and 3, pushes 3 → + pops 3 and 2, pushes 5 → push 9 → - pops 9 and 5, pushes 5 − 9 = −4.

Prefix evaluation

Prefix works the same way but scanning right to left, and the first value popped is the left operand. Example: - + 2 * 3 1 9 evaluates to (2 + 3 × 1) − 9 = −4.

Chapter 9 · Stacks & Queues

Queue & Circular Queue

First in, first out: enqueue and dequeue, why a simple array queue wastes space, and how the circular queue fixes it — plus a linked-list queue.

A queue adds at one end (the rear) and removes from the other (the front): FIFO — First In, First Out. It models every real queue: people at a ticket counter, print jobs, network packets, processes waiting for the CPU.

10203040frontreardequeueenqueue
Enqueue at the rear, dequeue from the front. 10 arrived first, so it leaves first.
Operation Meaning Cost
enqueue(x) add x at the rear O(1)
dequeue() remove and return the front item O(1)
front() / peek() look at the front item O(1)
isEmpty(), isFull() status checks O(1)

The problem with a simple array queue

Use front and rear indexes into an array. Enqueue does a[++rear] = x; dequeue does front++. But after a few dequeues, the empty slots at the start of the array are never reused: the queue reports "full" when rear reaches the end, even if it is mostly empty.

_0_1_2403504frontrear
Linear queue after three dequeues: slots 0–2 are wasted, and rear is already at the end.

Circular queue

The fix: let the indexes wrap around to 0 using % capacity. The array behaves like a ring.

  • enqueue: rear = (rear + 1) % N; a[rear] = x;
  • dequeue: x = a[front]; front = (front + 1) % N;
  • keep a count to tell full from empty.
C
#include <stdio.h>
#define N 5

int q[N], front = 0, rear = -1, count = 0;

int enqueue(int x) {
    if (count == N) { printf("Queue full, cannot add %d\n", x); return 0; }
    rear = (rear + 1) % N;
    q[rear] = x;
    count++;
    return 1;
}

int dequeue(void) {
    if (count == 0) { printf("Queue empty\n"); return -1; }
    int x = q[front];
    front = (front + 1) % N;
    count--;
    return x;
}

void show(void) {
    printf("queue (front -> rear): ");
    for (int i = 0; i < count; i++) printf("%d ", q[(front + i) % N]);
    printf("  [front=%d rear=%d]\n", front, rear);
}

int main(void) {
    for (int i = 1; i <= 5; i++) enqueue(i * 10);
    show();
    enqueue(60);                         // full
    printf("dequeued %d\n", dequeue());
    printf("dequeued %d\n", dequeue());
    enqueue(60);                         // reuses slot 0
    enqueue(70);                         // reuses slot 1
    show();
    return 0;
}
Output
queue (front -> rear): 10 20 30 40 50   [front=0 rear=4]
Queue full, cannot add 60
dequeued 10
dequeued 20
queue (front -> rear): 30 40 50 60 70   [front=2 rear=1]
Try it Yourself

Linked-list queue

Keep pointers to both ends: enqueue at the tail, dequeue at the head. Both are O(1), and there is no fixed capacity.

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;
Node *front = NULL, *rear = NULL;

void enqueue(int x) {
    Node *n = malloc(sizeof(Node));
    n->data = x; n->next = NULL;
    if (rear == NULL) front = rear = n;
    else { rear->next = n; rear = n; }
}

int dequeue(void) {
    if (front == NULL) return -1;
    Node *t = front;
    int x = t->data;
    front = front->next;
    if (front == NULL) rear = NULL;      // queue became empty
    free(t);
    return x;
}

int main(void) {
    const char *jobs[] = {"report.pdf", "notes.docx", "photo.png"};
    for (int i = 0; i < 3; i++) { enqueue(i); printf("queued %s\n", jobs[i]); }
    int j;
    while ((j = dequeue()) != -1) printf("printing %s\n", jobs[j]);
    return 0;
}
Output
queued report.pdf
queued notes.docx
queued photo.png
printing report.pdf
printing notes.docx
printing photo.png
Try it Yourself

Stack vs queue

Stack Queue
Order LIFO FIFO
Insert at top rear
Remove from top front
Typical uses undo, recursion, DFS, parsing scheduling, buffering, BFS

Chapter 10 · Stacks & Queues

Deque & Priority Queue

Two useful queue variations: the double-ended queue and the priority queue, with array-based implementations and where each one shines.

Deque (double-ended queue)

A deque (pronounced "deck") allows insertion and deletion at both ends. It can act as a stack or a queue.

Operation Effect
pushFront(x) / pushBack(x) insert at the front / rear
popFront() / popBack() remove from the front / rear

Special cases: an input-restricted deque allows insertion at one end only; an output-restricted deque allows deletion at one end only.

A circular array makes every deque operation O(1):

C
#include <stdio.h>
#define N 8

int d[N], front = 0, size = 0;

void pushBack(int x)  { d[(front + size) % N] = x; size++; }
void pushFront(int x) { front = (front - 1 + N) % N; d[front] = x; size++; }
int popFront(void)    { int x = d[front]; front = (front + 1) % N; size--; return x; }
int popBack(void)     { size--; return d[(front + size) % N]; }

void show(const char *msg) {
    printf("%-14s [", msg);
    for (int i = 0; i < size; i++) printf(i ? " %d" : "%d", d[(front + i) % N]);
    printf("]\n");
}

int main(void) {
    pushBack(20); pushBack(30); show("pushBack x2:");
    pushFront(10); show("pushFront 10:");
    pushBack(40); show("pushBack 40:");
    printf("popFront -> %d\n", popFront());
    printf("popBack  -> %d\n", popBack());
    show("now:");
    return 0;
}
Output
pushBack x2:   [20 30]
pushFront 10:  [10 20 30]
pushBack 40:   [10 20 30 40]
popFront -> 10
popBack  -> 40
now:           [20 30]
Try it Yourself

Priority queue

In a priority queue, each element has a priority, and dequeue always removes the element with the highest priority (or lowest, for a min-priority queue) — not the oldest. Hospital emergency rooms, CPU scheduling and Dijkstra's shortest-path algorithm all use one.

Possible implementations:

Implementation Insert Remove highest
Unsorted array O(1) O(n) — scan for the max
Sorted array O(n) — shift into place O(1)
Binary heap O(log n) O(log n)

A sorted array is simple and fine for small inputs:

C
#include <stdio.h>

typedef struct { char name[12]; int priority; } Patient;
Patient pq[10];
int n = 0;

void insert(const char *name, int pr) {           // keep sorted by priority, highest last
    int i = n - 1;
    while (i >= 0 && pq[i].priority > pr) { pq[i + 1] = pq[i]; i--; }
    snprintf(pq[i + 1].name, sizeof pq[i + 1].name, "%s", name);
    pq[i + 1].priority = pr;
    n++;
}

Patient removeMax(void) { return pq[--n]; }

int main(void) {
    insert("Anil", 2);     // 1 = mild ... 5 = critical
    insert("Bhavna", 5);
    insert("Chetan", 1);
    insert("Divya", 4);
    while (n > 0) {
        Patient p = removeMax();
        printf("treating %-7s (priority %d)\n", p.name, p.priority);
    }
    return 0;
}
Output
treating Bhavna  (priority 5)
treating Divya   (priority 4)
treating Anil    (priority 2)
treating Chetan  (priority 1)
Try it Yourself

For large inputs, use a binary heap, which gives O(log n) for both operations — covered in Heaps & Heap Sort.

Chapter 11 · Trees

Trees & Binary Trees

Hierarchical data: tree vocabulary, types of binary trees, array and linked representations, and the four traversals — inorder, preorder, postorder and level order.

A tree stores data in a hierarchy: one root at the top, and every other node has exactly one parent. File systems, the HTML of a web page, an organisation chart and a family tree are all trees.

DEBFGCA
A binary tree with root A. B and C are A's children; D, E, F and G are leaves.

Vocabulary

Term Meaning (for the tree above)
Root the top node with no parent — A
Parent / child B is the parent of D and E
Siblings nodes with the same parent — D and E
Leaf a node with no children — D, E, F, G
Internal node a node with at least one child — A, B, C
Edge a link between parent and child (a tree with n nodes has n − 1 edges)
Depth of a node edges from the root to it — depth(D) = 2
Height of a tree edges on the longest root-to-leaf path — 2 here
Degree of a node number of children — degree(A) = 2
Subtree a node together with all its descendants

Binary trees

A binary tree is a tree where each node has at most two children, called left and right.

Type Definition
Full (strict) every node has 0 or 2 children
Perfect full, and all leaves at the same level: 2ʰ⁺¹ − 1 nodes
Complete every level full except possibly the last, which is filled left to right
Skewed every node has only one child — basically a linked list
Balanced heights of left and right subtrees differ by at most 1 at every node

Representing a binary tree

Linked representation — each node holds data plus left and right pointers:

C
typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

Array representation — store level by level. For the node at index i (0-based): left child at 2i + 1, right child at 2i + 2, parent at (i − 1) / 2. Perfect for complete trees (like heaps); wasteful for skewed ones.

A0B1C2D3E4F5G6
The tree above stored level by level. B is at index 1, so its children are at 3 (D) and 4 (E).

Traversals

A traversal visits every node once. Depth-first traversals differ only in when you visit the node relative to its subtrees:

Traversal Order Result for the tree above
Preorder Node, Left, Right A B D E C F G
Inorder Left, Node, Right D B E A F C G
Postorder Left, Right, Node D E B F G C A
Level order level by level, left to right (uses a queue) A B C D E F G
C
#include <stdio.h>
#include <stdlib.h>

typedef struct T { char data; struct T *left, *right; } T;

T *node(char d, T *l, T *r) { T *t = malloc(sizeof(T)); t->data = d; t->left = l; t->right = r; return t; }

void preorder(T *t)  { if (!t) return; printf("%c ", t->data); preorder(t->left); preorder(t->right); }
void inorder(T *t)   { if (!t) return; inorder(t->left); printf("%c ", t->data); inorder(t->right); }
void postorder(T *t) { if (!t) return; postorder(t->left); postorder(t->right); printf("%c ", t->data); }

void levelOrder(T *root) {
    T *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        T *t = queue[front++];
        printf("%c ", t->data);
        if (t->left)  queue[rear++] = t->left;
        if (t->right) queue[rear++] = t->right;
    }
}

int height(T *t) {
    if (!t) return -1;                         // empty tree has height -1
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}
int count(T *t)  { return t ? 1 + count(t->left) + count(t->right) : 0; }
int leaves(T *t) { return !t ? 0 : (!t->left && !t->right) ? 1 : leaves(t->left) + leaves(t->right); }

int main(void) {
    T *root = node('A', node('B', node('D', NULL, NULL), node('E', NULL, NULL)),
                        node('C', node('F', NULL, NULL), node('G', NULL, NULL)));
    printf("Preorder:    "); preorder(root);   printf("\n");
    printf("Inorder:     "); inorder(root);    printf("\n");
    printf("Postorder:   "); postorder(root);  printf("\n");
    printf("Level order: "); levelOrder(root); printf("\n");
    printf("Height %d, nodes %d, leaves %d\n", height(root), count(root), leaves(root));
    return 0;
}
Output
Preorder:    A B D E C F G 
Inorder:     D B E A F C G 
Postorder:   D E B F G C A 
Level order: A B C D E F G 
Height 2, nodes 7, leaves 4
Try it Yourself

Rebuilding a tree from traversals

Given inorder + preorder (or inorder + postorder), the tree is unique:

  1. The first preorder element (or last postorder element) is the root.
  2. Find the root in the inorder sequence: everything to its left is the left subtree, everything to its right is the right subtree.
  3. Repeat for each subtree.

Preorder + postorder alone is not enough unless the tree is full.

Chapter 12 · Trees

Binary Search Tree

A binary tree that keeps itself sorted: search, insert, find min and max, and the three cases of deletion — plus why balance matters.

A binary search tree (BST) is a binary tree with one rule at every node:

All keys in the left subtree are smaller, and all keys in the right subtree are larger.

20403060807050
A BST. Every key left of 50 is smaller than 50; every key right of 50 is larger. The same holds at 30 and 70.

Because of that rule, an inorder traversal of a BST prints the keys in sorted order, and searching can discard half the remaining tree at each step — like binary search.

Try it

Insert, search and delete keys, and watch the tree and its traversals update:

Search and insert

To search, start at the root: go left if the key is smaller, right if it is larger, stop if equal. Insertion searches for the key and attaches a new leaf where the search fell off the tree.

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *left, *right; } Node;

Node *insert(Node *root, int key) {
    if (root == NULL) {
        Node *n = malloc(sizeof(Node));
        n->key = key; n->left = n->right = NULL;
        return n;
    }
    if (key < root->key)      root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                                  // duplicates are ignored
}

Node *search(Node *root, int key) {
    while (root != NULL && root->key != key)
        root = (key < root->key) ? root->left : root->right;
    return root;
}

void inorder(Node *r) { if (r) { inorder(r->left); printf("%d ", r->key); inorder(r->right); } }

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 35};
    Node *root = NULL;
    for (int i = 0; i < 8; i++) root = insert(root, keys[i]);
    printf("Inorder (sorted): ");
    inorder(root);
    printf("\n");
    printf("search 60: %s\n", search(root, 60) ? "found" : "not found");
    printf("search 65: %s\n", search(root, 65) ? "found" : "not found");
    return 0;
}
Output
Inorder (sorted): 20 30 35 40 50 60 70 80 
search 60: found
search 65: not found
Try it Yourself

Minimum and maximum

The smallest key is the leftmost node; the largest is the rightmost:

C
Node *minNode(Node *r) { while (r && r->left)  r = r->left;  return r; }
Node *maxNode(Node *r) { while (r && r->right) r = r->right; return r; }

Deletion: three cases

  1. Leaf — just remove it.
  2. One child — replace the node with its child.
  3. Two children — replace the node's key with its inorder successor (the smallest key in its right subtree), then delete that successor from the right subtree. (The inorder predecessor works too.)
C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *left, *right; } Node;

Node *insert(Node *r, int k) {
    if (!r) { r = malloc(sizeof(Node)); r->key = k; r->left = r->right = NULL; return r; }
    if (k < r->key) r->left = insert(r->left, k); else if (k > r->key) r->right = insert(r->right, k);
    return r;
}

Node *deleteKey(Node *root, int key) {
    if (root == NULL) return NULL;
    if (key < root->key)      root->left = deleteKey(root->left, key);
    else if (key > root->key) root->right = deleteKey(root->right, key);
    else {
        if (root->left == NULL)  { Node *r = root->right; free(root); return r; }   // cases 1 and 2
        if (root->right == NULL) { Node *l = root->left;  free(root); return l; }
        Node *succ = root->right;                                                   // case 3
        while (succ->left) succ = succ->left;
        root->key = succ->key;
        root->right = deleteKey(root->right, succ->key);
    }
    return root;
}

void preorder(Node *r) { if (r) { printf("%d ", r->key); preorder(r->left); preorder(r->right); } }

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    Node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    printf("start:            "); preorder(root); printf("\n");
    root = deleteKey(root, 20);  printf("delete 20 (leaf): "); preorder(root); printf("\n");
    root = deleteKey(root, 30);  printf("delete 30 (one):  "); preorder(root); printf("\n");
    root = deleteKey(root, 50);  printf("delete 50 (two):  "); preorder(root); printf("\n");
    return 0;
}
Output
start:            50 30 20 40 70 60 80 
delete 20 (leaf): 50 30 40 70 60 80 
delete 30 (one):  50 40 70 60 80 
delete 50 (two):  60 40 70 80
Try it Yourself

After deleting 50, its inorder successor 60 takes its place as the new root.

Why balance matters

Every BST operation costs O(h), where h is the height.

  • A balanced BST with n keys has height about log₂ n → operations are O(log n).
  • Insert keys in sorted order (10, 20, 30, 40…) and every new key goes right: the tree becomes a skewed chain with height n − 1 → O(n), no better than a linked list.
40302010
Inserting 10, 20, 30, 40 in order produces a skewed BST — effectively a linked list.

That is why self-balancing trees such as AVL trees (next lesson) and red-black trees exist.

Operation Balanced BST Skewed BST
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Inorder traversal O(n) O(n)

Chapter 13 · Trees

AVL Trees

Self-balancing BSTs: balance factors, the four rotation cases (LL, RR, LR, RL), and an insertion that stays O(log n) whatever order the keys arrive in.

An AVL tree (named after Adelson-Velsky and Landis, 1962) is a BST that keeps itself balanced. After every insertion or deletion it checks each node's balance factor and fixes any imbalance with rotations.

Balance factor

balance factor = height(left subtree) − height(right subtree)

In an AVL tree, every node's balance factor must be −1, 0 or +1. If an insertion makes some node's balance factor +2 or −2, that node is rebalanced. This keeps the height at most about 1.44 log₂ n, so search, insert and delete are all O(log n) guaranteed.

The four imbalance cases

Let Z be the lowest unbalanced node on the path from the inserted key up to the root.

Case Inserted into Fix
LL left subtree of Z's left child one right rotation at Z
RR right subtree of Z's right child one left rotation at Z
LR right subtree of Z's left child left rotation at the child, then right rotation at Z
RL left subtree of Z's right child right rotation at the child, then left rotation at Z

LL case: right rotation

Inserting 30, 20, 10 makes 30 left-heavy (balance factor +2):

102030
Before: 30 has balance factor +2 (left-heavy).

Rotate right at 30: the left child 20 moves up to become the root, 30 moves down to become 20's right child, and 20's old right subtree (empty here) becomes 30's new left subtree.

103020
After one right rotation the tree is balanced.

RR case: left rotation

Inserting 10, 20, 30 is the mirror image: rotate left at 10 and 20 becomes the root.

LR case: double rotation

Inserting 30, 10, 20: the imbalance is at 30 (left-heavy), but the new key went into the right of the left child. A single right rotation would not fix it. First rotate left at 10 (turning it into the LL case), then rotate right at 30. The result is again 20 with children 10 and 30.

Insertion in C

C
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key, height; struct Node *left, *right; } Node;

int h(Node *n) { return n ? n->height : 0; }
int max(int a, int b) { return a > b ? a : b; }
void update(Node *n) { n->height = 1 + max(h(n->left), h(n->right)); }
int balance(Node *n) { return n ? h(n->left) - h(n->right) : 0; }

Node *rotateRight(Node *z) {
    Node *y = z->left, *t = y->right;
    y->right = z;
    z->left = t;
    update(z); update(y);
    return y;
}

Node *rotateLeft(Node *z) {
    Node *y = z->right, *t = y->left;
    y->left = z;
    z->right = t;
    update(z); update(y);
    return y;
}

Node *insert(Node *n, int key) {
    if (!n) { n = malloc(sizeof(Node)); n->key = key; n->height = 1; n->left = n->right = NULL; return n; }
    if (key < n->key) n->left = insert(n->left, key);
    else if (key > n->key) n->right = insert(n->right, key);
    else return n;

    update(n);
    int b = balance(n);
    if (b > 1 && key < n->left->key)  { printf("  LL at %d\n", n->key); return rotateRight(n); }
    if (b < -1 && key > n->right->key) { printf("  RR at %d\n", n->key); return rotateLeft(n); }
    if (b > 1 && key > n->left->key)  { printf("  LR at %d\n", n->key); n->left = rotateLeft(n->left); return rotateRight(n); }
    if (b < -1 && key < n->right->key) { printf("  RL at %d\n", n->key); n->right = rotateRight(n->right); return rotateLeft(n); }
    return n;
}

void preorder(Node *r) { if (r) { printf("%d ", r->key); preorder(r->left); preorder(r->right); } }

int main(void) {
    int keys[] = {10, 20, 30, 40, 50, 25};
    Node *root = NULL;
    for (int i = 0; i < 6; i++) {
        printf("insert %d\n", keys[i]);
        root = insert(root, keys[i]);
    }
    printf("Preorder: ");
    preorder(root);
    printf("\nHeight: %d (a plain BST built from the same keys has height 5)\n", h(root));
    return 0;
}
Output
insert 10
insert 20
insert 30
  RR at 10
insert 40
insert 50
  RR at 30
insert 25
  RL at 20
Preorder: 30 20 10 25 40 50 
Height: 3 (a plain BST built from the same keys has height 5)
Try it Yourself

The final AVL tree for 10, 20, 30, 40, 50, 25:

102520504030
Sorted-ish input that would make a plain BST a chain stays balanced with height 3 (counting nodes).

Chapter 14 · Trees

Heaps & Heap Sort

Complete binary trees stored in arrays: max-heaps and min-heaps, insert with sift-up, extract with sift-down, building a heap in O(n), and heap sort.

A binary heap is a complete binary tree with the heap property:

  • Max-heap: every parent ≥ its children, so the largest key is at the root.
  • Min-heap: every parent ≤ its children, so the smallest key is at the root.

Unlike a BST, a heap says nothing about left versus right — only parent versus child.

40507030608090
A max-heap. Every parent is larger than its children; 90, the maximum, is the root.

Stored in an array

Because a heap is complete, it fits perfectly in an array with no gaps — no pointers needed. For index i (0-based): parent (i − 1) / 2, left child 2i + 1, right child 2i + 2.

900701802403504305606
The same heap stored level by level.

Insert: add at the end, then sift up

Put the new key in the next free slot (keeping the tree complete), then swap it with its parent while it is larger. At most one swap per level: O(log n).

Extract max: move the last key to the root, then sift down

Remove the root (the maximum). Move the last element to the root, then swap it with its larger child while it is smaller than that child. Also O(log n).

C
#include <stdio.h>

int heap[100], n = 0;

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void siftUp(int i) {
    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        swap(&heap[(i - 1) / 2], &heap[i]);
        i = (i - 1) / 2;
    }
}

void siftDown(int i) {
    for (;;) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && heap[l] > heap[largest]) largest = l;
        if (r < n && heap[r] > heap[largest]) largest = r;
        if (largest == i) return;
        swap(&heap[i], &heap[largest]);
        i = largest;
    }
}

void insert(int key) { heap[n] = key; siftUp(n); n++; }

int extractMax(void) {
    int top = heap[0];
    heap[0] = heap[--n];
    siftDown(0);
    return top;
}

void show(void) { for (int i = 0; i < n; i++) printf("%d ", heap[i]); printf("\n"); }

int main(void) {
    int keys[] = {40, 70, 30, 90, 50, 80, 60};
    for (int i = 0; i < 7; i++) insert(keys[i]);
    printf("heap array: "); show();
    printf("extract: %d\n", extractMax());
    printf("heap array: "); show();
    printf("extract all: ");
    while (n > 0) printf("%d ", extractMax());
    printf("\n");
    return 0;
}
Output
heap array: 90 70 80 40 50 30 60 
extract: 90
heap array: 80 70 60 40 50 30 
extract all: 80 70 60 50 40 30
Try it Yourself

Building a heap in O(n)

Inserting n keys one by one costs O(n log n). Heapify does better: start from the last internal node (index n/2 − 1) and sift each node down, moving towards the root. Most nodes are near the bottom and sift down only a little, which adds up to O(n).

Heap sort

  1. Build a max-heap from the array — O(n).
  2. Repeatedly swap the root (maximum) with the last element of the heap, shrink the heap by one, and sift the new root down — n × O(log n).

Total O(n log n) in every case, using O(1) extra space. It is not stable.

C
#include <stdio.h>

void siftDown(int a[], int n, int i) {
    for (;;) {
        int big = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        int t = a[i]; a[i] = a[big]; a[big] = t;
        i = big;
    }
}

void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);      // build max-heap
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;                 // move max to the end
        siftDown(a, end, 0);                                     // fix the smaller heap
    }
}

int main(void) {
    int a[] = {12, 3, 45, 7, 23, 9, 31, 1};
    heapSort(a, 8);
    for (int i = 0; i < 8; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
Output
1 3 7 9 12 23 31 45
Try it Yourself

Heap operation costs

Operation Cost
Find max (max-heap) O(1)
Insert O(log n)
Extract max O(log n)
Build heap from n keys O(n)
Heap sort O(n log n)

Heaps are the standard way to implement priority queues — used in Dijkstra's shortest paths, Prim's MST, CPU scheduling and "top-k" problems.

Chapter 15 · Graphs & Hashing

Graphs: Terminology & Representation

Vertices and edges: directed, weighted and connected graphs, degree, paths and cycles, and storing graphs as adjacency matrices and adjacency lists.

A graph G = (V, E) is a set of vertices (nodes) V connected by edges E. Graphs model anything with connections: road maps, social networks, the web, course prerequisites, computer networks.

ABCDE
An undirected graph with 5 vertices and 6 edges.

Vocabulary

Term Meaning
Undirected graph edges have no direction: A–B means both ways
Directed graph (digraph) edges are arrows: A → B does not imply B → A
Weighted graph each edge carries a number (distance, cost, time)
Adjacent two vertices joined by an edge
Degree number of edges at a vertex; in digraphs, in-degree and out-degree
Path a sequence of vertices joined by edges
Cycle a path that starts and ends at the same vertex
Connected there is a path between every pair of vertices
Tree a connected graph with no cycles (n vertices, n − 1 edges)
DAG directed acyclic graph — a digraph with no directed cycles

Directed and weighted graphs

42158SABT
A weighted directed graph. Shortest-path algorithms like Dijkstra's work on graphs like this.

Representation 1: adjacency matrix

A V × V grid where adj[i][j] = 1 (or the weight) if there is an edge from i to j.

ABCDEA01100B10011C10010D01101E01010
Adjacency matrix of the first graph. It is symmetric because the graph is undirected.
  • Check "is there an edge i–j?" in O(1).
  • Uses O(V²) memory even if there are few edges.
  • Listing a vertex's neighbours takes O(V).

Representation 2: adjacency list

An array of lists: adj[i] holds the neighbours of vertex i.

Text
A: B C
B: A D E
C: A D
D: B C E
E: B D
  • Uses O(V + E) memory — ideal for sparse graphs (most real graphs).
  • Listing neighbours is fast: O(degree).
  • Checking a specific edge takes O(degree).
C
#include <stdio.h>
#include <stdlib.h>

typedef struct Edge { int to; struct Edge *next; } Edge;

#define V 5
Edge *adj[V];
const char *name = "ABCDE";

void addEdge(int u, int v) {                 // undirected: add both directions
    Edge *e = malloc(sizeof(Edge)); e->to = v; e->next = adj[u]; adj[u] = e;
    e = malloc(sizeof(Edge));       e->to = u; e->next = adj[v]; adj[v] = e;
}

int main(void) {
    int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {1, 4}};
    for (int i = 0; i < 6; i++) addEdge(edges[i][0], edges[i][1]);

    int matrix[V][V] = {0};
    for (int u = 0; u < V; u++) {
        printf("%c:", name[u]);
        int deg = 0;
        for (Edge *e = adj[u]; e; e = e->next) { printf(" %c", name[e->to]); matrix[u][e->to] = 1; deg++; }
        printf("  -> degree %d\n", deg);
    }
    printf("\nAdjacency matrix:\n  ");
    for (int j = 0; j < V; j++) printf(" %c", name[j]);
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("%c ", name[i]);
        for (int j = 0; j < V; j++) printf(" %d", matrix[i][j]);
        printf("\n");
    }
    return 0;
}
Output
A: C B  -> degree 2
B: E D A  -> degree 3
C: D A  -> degree 2
D: E C B  -> degree 3
E: B D  -> degree 2

Adjacency matrix:
   A B C D E
A  0 1 1 0 0
B  1 0 0 1 1
C  1 0 0 1 0
D  0 1 1 0 1
E  0 1 0 1 0
Try it Yourself

(The list shows neighbours in reverse insertion order because each new edge is added at the head of the list.)

Matrix or list?

Adjacency matrix Adjacency list
Memory O(V²) O(V + E)
Is (u, v) an edge? O(1) O(deg(u))
Visit all neighbours of u O(V) O(deg(u))
Best for dense graphs, quick edge checks sparse graphs, traversals

Chapter 16 · Graphs & Hashing

Graph Traversal: BFS & DFS

Explore a graph level by level with a queue (BFS) or as deep as possible with a stack or recursion (DFS) — with step-by-step traces, shortest paths and applications.

To traverse a graph is to visit every vertex reachable from a starting vertex. Unlike a tree, a graph can have cycles, so we keep a visited array to avoid looping forever.

Breadth-first search (BFS)

BFS visits the start, then all its neighbours, then all their unvisited neighbours — expanding outward in rings, like ripples in water. It uses a queue.

  1. Mark the start visited and enqueue it.
  2. While the queue is not empty: dequeue a vertex, visit it, and enqueue each unvisited neighbour (marking it visited).

Depth-first search (DFS)

DFS goes as deep as possible along one path before backtracking. It uses a stack — usually the call stack, via recursion.

  1. Visit the vertex and mark it visited.
  2. For each unvisited neighbour, recursively DFS from it.

Step through both

Pick a start vertex and step through BFS or DFS. Watch the queue or stack and the visit order:

BFS and DFS in C

C
#include <stdio.h>

#define V 7
int adj[V][V];
const char *name = "ABCDEFG";
int visited[V];

void addEdge(int u, int v) { adj[u][v] = adj[v][u] = 1; }

void bfs(int start) {
    int queue[V], front = 0, rear = 0, dist[V];
    for (int i = 0; i < V; i++) visited[i] = 0;
    visited[start] = 1; dist[start] = 0;
    queue[rear++] = start;
    printf("BFS: ");
    while (front < rear) {
        int u = queue[front++];
        printf("%c(%d) ", name[u], dist[u]);
        for (int v = 0; v < V; v++)
            if (adj[u][v] && !visited[v]) {
                visited[v] = 1;
                dist[v] = dist[u] + 1;      // one more edge than its parent
                queue[rear++] = v;
            }
    }
    printf("\n");
}

void dfs(int u) {
    visited[u] = 1;
    printf("%c ", name[u]);
    for (int v = 0; v < V; v++)
        if (adj[u][v] && !visited[v]) dfs(v);
}

int main(void) {
    // A-B, A-C, B-D, B-E, C-F, E-F, F-G
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 5}, {5, 6}};
    for (int i = 0; i < 7; i++) addEdge(e[i][0], e[i][1]);
    bfs(0);
    for (int i = 0; i < V; i++) visited[i] = 0;
    printf("DFS: ");
    dfs(0);
    printf("\n");
    return 0;
}
Output
BFS: A(0) B(1) C(1) D(2) E(2) F(2) G(3) 
DFS: A B D E F C G
Try it Yourself

The number in brackets after each BFS vertex is its distance (in edges) from A — BFS finds shortest paths in unweighted graphs.

ABCDEFG
The graph used in the program. BFS from A: A B C D E F G. DFS from A: A B D E F C G.

BFS vs DFS

BFS DFS
Data structure queue stack / recursion
Explores level by level one branch to the end, then backtracks
Shortest path (unweighted) yes no
Memory can hold a whole level holds one path
Time O(V + E) with a list, O(V²) with a matrix same
Typical uses shortest paths, nearest neighbours, web crawling, social "degrees of separation" cycle detection, topological sort, connected components, mazes, backtracking

Applications

  • Connected components: run DFS/BFS from every unvisited vertex; each run discovers one component.
  • Cycle detection: in DFS, reaching a visited vertex that is not your parent means a cycle (undirected graphs).
  • Topological sort of a DAG: output vertices in reverse order of DFS completion — see Graph Algorithms.
  • Bipartite check: BFS-colour vertices in two colours; a conflict means not bipartite.

Chapter 17 · Graphs & Hashing

Hashing

Near O(1) search with hash tables: hash functions, collisions, separate chaining, linear and quadratic probing, double hashing and the load factor.

Arrays give O(1) access by index. What if you could turn any key — a roll number, a name — into an index? That is hashing: a hash function converts a key into an index of an array called a hash table.

Text
h(key) = key % tableSize

h(23) = 23 % 10 = 3   -> store 23 in slot 3
h(47) = 47 % 10 = 7   -> store 47 in slot 7

Search, insert and delete then take O(1) on average.

Good hash functions

A good hash function is fast, deterministic, and spreads keys uniformly over the table.

Method Formula Notes
Division h(k) = k mod m choose m prime, away from powers of 2
Multiplication h(k) = ⌊m × frac(k × A)⌋, 0 < A < 1 m can be anything
Mid-square square k, take the middle digits old textbook method
Folding split k into parts and add them for long keys like phone numbers
Strings h = h × 31 + c for each character how Java hashes strings

Collisions

Two keys can hash to the same slot: with m = 10, both 23 and 33 go to slot 3. That is a collision, and every hash table needs a strategy for it.

Separate chaining

Each slot holds a linked list of all keys that hash there.

07001508592237310145676
Separate chaining with h(k) = k mod 7. 50, 85 and 92 all hash to slot 1 and share a chain.
C
#include <stdio.h>
#include <stdlib.h>

#define M 7
typedef struct Node { int key; struct Node *next; } Node;
Node *table[M];

int h(int k) { return k % M; }

void insert(int k) {
    Node *n = malloc(sizeof(Node));
    n->key = k;
    n->next = NULL;
    Node **p = &table[h(k)];
    while (*p) p = &(*p)->next;       // walk to the end of the chain
    *p = n;
}

int search(int k) {
    for (Node *p = table[h(k)]; p; p = p->next)
        if (p->key == k) return 1;
    return 0;
}

int main(void) {
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    for (int i = 0; i < 7; i++) insert(keys[i]);
    for (int i = 0; i < M; i++) {
        printf("%d:", i);
        for (Node *p = table[i]; p; p = p->next) printf(" %d ->", p->key);
        printf(" NULL\n");
    }
    printf("search 92: %s, search 15: %s\n", search(92) ? "found" : "missing", search(15) ? "found" : "missing");
    return 0;
}
Output
0: 700 -> NULL
1: 50 -> 85 -> 92 -> NULL
2: NULL
3: 73 -> 101 -> NULL
4: NULL
5: NULL
6: 76 -> NULL
search 92: found, search 15: missing
Try it Yourself

Open addressing

All keys live inside the array. On a collision, probe other slots in a fixed sequence until an empty one is found.

Probing Try slots Weakness
Linear h, h+1, h+2, … (mod m) primary clustering — long runs of filled slots
Quadratic h, h+1², h+2², h+3², … secondary clustering; may miss empty slots
Double hashing h, h + h₂(k), h + 2·h₂(k), … best spread; needs h₂(k) ≠ 0
07001502853924735101676
The same keys with linear probing. 85 wanted slot 1 (taken by 50) and moved to 2; 92 wanted 1 and ended in 3.

Try it

Insert keys and compare chaining, linear probing and quadratic probing:

C
#include <stdio.h>

#define M 7
int table[M];

void insert(int k) {
    for (int i = 0; i < M; i++) {
        int slot = (k % M + i) % M;              // linear probing
        if (table[slot] == -1) {
            table[slot] = k;
            printf("%3d -> slot %d%s\n", k, slot, i ? " (after collision)" : "");
            return;
        }
    }
    printf("table full, cannot insert %d\n", k);
}

int main(void) {
    for (int i = 0; i < M; i++) table[i] = -1;
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    for (int i = 0; i < 7; i++) insert(keys[i]);
    return 0;
}
Output
 50 -> slot 1
700 -> slot 0
 76 -> slot 6
 85 -> slot 2 (after collision)
 92 -> slot 3 (after collision)
 73 -> slot 4 (after collision)
101 -> slot 5 (after collision)
Try it Yourself

Load factor and rehashing

The load factor α = n / m (keys stored ÷ table size) measures how full the table is.

  • Chaining: average chain length is α, so keep α around 1.
  • Open addressing: performance falls sharply as α approaches 1; keep α below about 0.7.
  • When α gets too high, rehash: allocate a table about twice the size and reinsert every key.

Costs

Average Worst case
Search / insert / delete O(1) O(n) — everything collides

Hash tables power dictionaries in Python, unordered_map in C++, database indexes, caches and compilers' symbol tables.

Chapter 18 · Searching & Sorting

Linear & Binary Search

Find things fast: linear search for any list, binary search for sorted ones — iterative and recursive versions, step-by-step traces and the classic off-by-one traps.

Linear search

Check every element from the start until you find the key. It works on any list, sorted or not.

  • Best case O(1), worst and average case O(n).

You wrote it in the Arrays lesson. Its weakness is speed on large data.

Binary search

If the array is sorted, you can do much better. Look at the middle element:

  • equal to the key → found;
  • key smaller → the key can only be in the left half;
  • key larger → it can only be in the right half.

Each step halves the search space, so at most about log₂ n steps are needed: O(log n). For a million elements that is 20 comparisons instead of a million.

Iterative binary search

C
#include <stdio.h>

int binarySearch(const int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;     // avoids overflow of (low + high)
        printf("  low=%d high=%d mid=%d a[mid]=%d\n", low, high, mid, a[mid]);
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;       // key is in the right half
        else high = mid - 1;                   // key is in the left half
    }
    return -1;
}

int main(void) {
    int a[] = {3, 8, 15, 21, 29, 34, 42, 57, 63, 78};
    int n = 10;
    printf("search 57:\n");
    printf("-> index %d\n", binarySearch(a, n, 57));
    printf("search 10:\n");
    printf("-> index %d\n", binarySearch(a, n, 10));
    return 0;
}
Output
search 57:
  low=0 high=9 mid=4 a[mid]=29
  low=5 high=9 mid=7 a[mid]=57
-> index 7
search 10:
  low=0 high=9 mid=4 a[mid]=29
  low=0 high=3 mid=1 a[mid]=8
  low=2 high=3 mid=2 a[mid]=15
-> index -1
Try it Yourself
3081152213294345426577638789lowmidhigh
Second step of the search for 57: the left half was discarded, and mid now lands on 57.

Recursive binary search

C
#include <stdio.h>

int bs(const int a[], int low, int high, int key) {
    if (low > high) return -1;                       // empty range: not found
    int mid = low + (high - low) / 2;
    if (a[mid] == key) return mid;
    return a[mid] < key ? bs(a, mid + 1, high, key) : bs(a, low, mid - 1, key);
}

int main(void) {
    int a[] = {2, 4, 7, 10, 23, 38, 56, 72, 91};
    int keys[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) printf("%d -> %d\n", keys[i], bs(a, 0, 8, keys[i]));
    return 0;
}
Output
23 -> 4
2 -> 0
91 -> 8
50 -> -1
Try it Yourself

Recurrence: T(n) = T(n/2) + O(1) → O(log n). The recursive version uses O(log n) stack space; the iterative one uses O(1).

Variants worth knowing

Binary search finds more than exact matches. Changing what happens on equality gives you the first or last occurrence of a repeated key:

C
#include <stdio.h>

int firstOccurrence(const int a[], int n, int key) {
    int low = 0, high = n - 1, ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { ans = mid; high = mid - 1; }   // record it, keep looking left
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}

int lastOccurrence(const int a[], int n, int key) {
    int low = 0, high = n - 1, ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { ans = mid; low = mid + 1; }    // keep looking right
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}

int main(void) {
    int a[] = {1, 3, 3, 3, 3, 5, 8, 8, 9};
    int f = firstOccurrence(a, 9, 3), l = lastOccurrence(a, 9, 3);
    printf("3 appears from index %d to %d: %d times\n", f, l, l - f + 1);
    return 0;
}
Output
3 appears from index 1 to 4: 4 times
Try it Yourself
Linear search Binary search
Needs sorted data no yes
Time O(n) O(log n)
Works on linked lists yes not efficiently (no random access)

Chapter 19 · Searching & Sorting

Bubble, Selection & Insertion Sort

The three O(n²) sorts: how each one works, passes and swaps traced by hand, stability, best cases, and when a simple sort is the right choice.

Sorting puts elements in order. Sorted data makes searching (binary search), finding duplicates, merging and reporting much easier. We start with three simple sorts that are easy to trace by hand — exactly what exams ask.

Watch them run on the same data:

Bubble sort

Compare adjacent pairs and swap if they are in the wrong order. After pass 1 the largest element has "bubbled" to the end; after pass 2, the second largest; and so on. If a pass makes no swaps, the array is already sorted and we can stop early.

C
#include <stdio.h>

void show(const int a[], int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }

void bubbleSort(int a[], int n) {
    for (int pass = 1; pass < n; pass++) {
        int swapped = 0;
        for (int j = 0; j < n - pass; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = 1;
            }
        printf("after pass %d: ", pass); show(a, n);
        if (!swapped) break;                 // no swaps: already sorted
    }
}

int main(void) {
    int a[] = {5, 1, 4, 2, 8};
    bubbleSort(a, 5);
    return 0;
}
Output
after pass 1: 1 4 2 5 8 
after pass 2: 1 2 4 5 8 
after pass 3: 1 2 4 5 8
Try it Yourself

Selection sort

Find the minimum of the unsorted part and swap it to the front of that part. Exactly n − 1 swaps — useful when writing to memory is expensive.

C
#include <stdio.h>

void show(const int a[], int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
        printf("pass %d (placed %d): ", i + 1, a[i]); show(a, n);
    }
}

int main(void) {
    int a[] = {64, 25, 12, 22, 11};
    selectionSort(a, 5);
    return 0;
}
Output
pass 1 (placed 11): 11 25 12 22 64 
pass 2 (placed 12): 11 12 25 22 64 
pass 3 (placed 22): 11 12 22 25 64 
pass 4 (placed 25): 11 12 22 25 64
Try it Yourself

Insertion sort

Build the sorted part one element at a time: take the next element (the key) and shift larger sorted elements right until the key's place is found — the way you sort playing cards in your hand.

C
#include <stdio.h>

void show(const int a[], int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];                 // shift right
            j--;
        }
        a[j + 1] = key;
        printf("insert %2d: ", key); show(a, n);
    }
}

int main(void) {
    int a[] = {12, 11, 13, 5, 6};
    insertionSort(a, 5);
    return 0;
}
Output
insert 11: 11 12 13 5 6 
insert 13: 11 12 13 5 6 
insert  5: 5 11 12 13 6 
insert  6: 5 6 11 12 13
Try it Yourself

On nearly sorted data, insertion sort barely shifts anything and runs in close to O(n) — which is why fast library sorts switch to insertion sort for small pieces.

Comparison

Bubble Selection Insertion
Best case O(n) (with early exit) O(n²) O(n)
Average / worst O(n²) O(n²) O(n²)
Swaps / writes many n − 1 swaps many shifts
Extra space O(1) O(1) O(1)
Stable? yes no yes
Adaptive (faster on sorted input)? yes no yes

Chapter 20 · Searching & Sorting

Merge, Quick & Counting Sort

Faster sorting: divide-and-conquer merge sort and quick sort with their partition traces, plus counting and radix sort that beat O(n log n) on integers.

The O(n²) sorts are fine for a few hundred elements. For a million, you need O(n log n). Both merge sort and quick sort get there with divide and conquer: split the problem, solve the pieces recursively, combine.

Merge sort

  1. Divide the array into two halves.
  2. Conquer: sort each half recursively.
  3. Combine: merge the two sorted halves (the two-pointer merge from the Arrays lesson).
C
#include <stdio.h>

void merge(int a[], int lo, int mid, int hi) {
    int tmp[64], i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= keeps it stable
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = 0; k < hi - lo + 1; k++) a[lo + k] = tmp[k];
}

void mergeSort(int a[], int lo, int hi, int depth) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, depth + 1);
    mergeSort(a, mid + 1, hi, depth + 1);
    merge(a, lo, mid, hi);
    printf("%*smerged [%d..%d]: ", depth * 2, "", lo, hi);
    for (int i = lo; i <= hi; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(a, 0, 6, 0);
    return 0;
}
Output
    merged [0..1]: 27 38 
    merged [2..3]: 3 43 
  merged [0..3]: 3 27 38 43 
    merged [4..5]: 9 82 
  merged [4..6]: 9 10 82 
merged [0..6]: 3 9 10 27 38 43 82
Try it Yourself

Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n) in every case. The merge needs an O(n) temporary array. Merge sort is stable and is the standard choice for sorting linked lists and huge files on disk.

Quick sort

  1. Pick a pivot element.
  2. Partition: rearrange so everything smaller than the pivot is on its left and everything larger on its right. The pivot is now in its final position.
  3. Recursively sort the left and right parts. No merge step is needed.

The Lomuto partition uses the last element as the pivot:

C
#include <stdio.h>

void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(&a[++i], &a[j]);   // grow the "smaller" region
    swap(&a[i + 1], &a[hi]);                      // put the pivot between the regions
    return i + 1;
}

void quickSort(int a[], int lo, int hi, int n) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    printf("pivot %2d -> index %d: ", a[p], p);
    for (int i = 0; i < n; i++) printf(i == p ? "[%d] " : "%d ", a[i]);
    printf("\n");
    quickSort(a, lo, p - 1, n);
    quickSort(a, p + 1, hi, n);
}

int main(void) {
    int a[] = {10, 80, 30, 90, 40, 50, 70};
    quickSort(a, 0, 6, 7);
    return 0;
}
Output
pivot 70 -> index 4: 10 30 40 50 [70] 90 80 
pivot 50 -> index 3: 10 30 40 [50] 70 90 80 
pivot 40 -> index 2: 10 30 [40] 50 70 90 80 
pivot 30 -> index 1: 10 [30] 40 50 70 90 80 
pivot 80 -> index 5: 10 30 40 50 70 [80] 90
Try it Yourself
Case When Cost
Best / average pivot splits roughly in half O(n log n)
Worst pivot is always the smallest or largest (e.g. sorted input with last-element pivot) O(n²)

Choosing a random pivot or the median of three makes the worst case extremely unlikely. In practice quick sort is often the fastest comparison sort: it sorts in place (O(log n) stack space) and is cache-friendly. It is not stable.

Counting sort

When keys are small integers in a known range 0…k, you do not need comparisons at all. Count how many times each value occurs, then write the values out in order: O(n + k).

C
#include <stdio.h>

int main(void) {
    int a[] = {4, 2, 2, 8, 3, 3, 1, 7, 2};
    int n = 9, k = 8, count[9] = {0};
    for (int i = 0; i < n; i++) count[a[i]]++;
    int idx = 0;
    for (int v = 0; v <= k; v++)
        while (count[v]--) a[idx++] = v;
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
Output
1 2 2 2 3 3 4 7 8
Try it Yourself

Radix sort applies a stable counting sort digit by digit (units, then tens, then hundreds…), sorting d-digit numbers in O(d × (n + 10)).

The big comparison

Algorithm Best Average Worst Space Stable
Bubble O(n) O(n²) O(n²) O(1) yes
Selection O(n²) O(n²) O(n²) O(1) no
Insertion O(n) O(n²) O(n²) O(1) yes
Merge O(n log n) O(n log n) O(n log n) O(n) yes
Quick O(n log n) O(n log n) O(n²) O(log n) no
Heap O(n log n) O(n log n) O(n log n) O(1) no
Counting O(n + k) O(n + k) O(n + k) O(k) yes

Chapter 21 · Searching & Sorting

Data Structures Cheat Sheet

Every structure and algorithm from CSE 102 on one page: operation costs, when to use what, key formulas and the programs to practise.

Operation costs

Structure Access Search Insert Delete Notes
Array O(1) O(n) O(n) O(n) O(1) at the end
Sorted array O(1) O(log n) O(n) O(n) binary search
Singly linked list O(n) O(n) O(1)* O(1)* *at head or after a known node
Doubly linked list O(n) O(n) O(1)* O(1)* delete with only the node pointer
Stack top only O(n) O(1) push O(1) pop LIFO
Queue front only O(n) O(1) enqueue O(1) dequeue FIFO
BST (balanced) — O(log n) O(log n) O(log n) O(n) if skewed
AVL tree — O(log n) O(log n) O(log n) guaranteed
Binary heap O(1) max/min O(n) O(log n) O(log n) extract priority queue
Hash table — O(1) avg O(1) avg O(1) avg O(n) worst
Graph (adj. list) — O(V + E) traversal O(1) edge O(deg) edge sparse graphs

Choosing a structure

You need to… Use
access by position, rarely insert array
insert/delete often in the middle linked list
undo, backtrack, match brackets, evaluate expressions stack
process in arrival order, BFS, scheduling queue
always get the smallest/largest next heap / priority queue
keep keys sorted with fast search balanced BST (AVL)
look up by key, fastest on average hash table
model connections or networks graph

Key formulas

Fact Formula
Max nodes at level l of a binary tree 2ˡ
Max nodes in a binary tree of height h 2ʰ⁺¹ − 1
Min height for n nodes ⌈log₂(n + 1)⌉ − 1
Heap/complete tree in an array (0-based) parent (i−1)/2, children 2i+1, 2i+2
AVL balance factor height(left) − height(right) ∈ {−1, 0, 1}
Edges in a tree with n vertices n − 1
Sum of degrees (undirected) 2 × edges
Max edges, simple undirected graph n(n − 1) / 2
Load factor of a hash table α = n / m
Circular queue next index (i + 1) % capacity

Sorting summary

Algorithm Average Worst Stable In place
Bubble / Insertion O(n²) O(n²) yes yes
Selection O(n²) O(n²) no yes
Merge O(n log n) O(n log n) yes no
Quick O(n log n) O(n²) no yes
Heap O(n log n) O(n log n) no yes
Counting O(n + k) O(n + k) yes no

Programs to practise

  1. Insert/delete at a position in an array.
  2. Singly linked list: insert at head, tail and position; delete by value; reverse; find middle; detect a cycle.
  3. Doubly and circular linked list insert and delete.
  4. Stack using an array and a linked list; balanced brackets; infix → postfix; postfix evaluation.
  5. Circular queue; queue using a linked list.
  6. Binary tree traversals (recursive), height, count leaves.
  7. BST insert, search, delete; check if a tree is a BST.
  8. Heap insert and extract; heap sort.
  9. BFS and DFS on an adjacency matrix and an adjacency list.
  10. Hash table with chaining and with linear probing.
  11. Linear and binary search; all six sorts.

Theory questions to prepare

  1. Classify data structures with examples; define ADT.
  2. Array vs linked list.
  3. Stack and queue applications; why a circular queue?
  4. Convert and evaluate an expression (show the stack table).
  5. Tree terminology; types of binary trees; traversals of a given tree.
  6. Construct a BST / AVL tree from a key sequence; show rotations.
  7. Heapify an array; trace heap sort.
  8. Adjacency matrix vs list; BFS vs DFS with a traced example.
  9. Hash functions and collision resolution; load factor.
  10. Compare sorting algorithms (table above); define stable and in-place.
Esc
↑↓ move↵ open