SyntaxPilot
Courses/C Programming/Lesson 24

C Programming · Lesson 24 of 30 · 15 min

Trees

queued

These are the notes for C episode 24. Last episode a linked list made inserting fast. This episode hits the thing a list is terrible at, searching, and you invent the fix: a binary search tree (BST), where every node has two pointers, one to the smaller values and one to the bigger values. Along the way you meet the tree vocabulary (root, parent, child, leaf, subtree, height), your first recursive functions, the three classic traversals, and a nasty trap: sorted input. Every example was compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13, the same command as the SyntaxPilot compiler) and run as shown. The online compiler stops a program after 8 seconds and reports Time Limit Exceeded.

The problem: the railway enquiry counter

Real-life example: a railway enquiry counter. The system holds a million bookings, numbered 1 to 1,000,000, kept in order. A passenger asks: "Is booking 734512 confirmed?" The clerk starts at booking 1 and checks them one by one until he reaches 734,512. That's over seven lakh checks for one question, and the counter gets a lakh (100,000) enquiries a day.

The bookings as a linked list (episode 22). The first loop adds a million nodes at the front, from 1,000,000 down to 1, so the list ends up in order. Then Q enquiries each pick a random booking with rand() and walk the list until they find it:

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

struct node {
    int pnr;
    struct node *next;
};

#define N 1000000
#define Q 10

int main() {
    struct node *head = NULL;
    for (int k = N; k >= 1; k--) {
        struct node *n = malloc(sizeof(struct node));
        n->pnr = k;
        n->next = head;
        head = n;
    }
    int found = 0;
    for (int q = 0; q < Q; q++) {
        int want = rand() % N + 1;
        for (struct node *p = head; p != NULL; p = p->next)
            if (p->pnr == want) {
                found++;
                break;
            }
    }
    printf("Bookings: %d, enquiries: %d, found: %d\n", N, Q, found);
    return 0;
}
Bookings: 1000000, enquiries: 10, found: 10

Instant. Now change Q to 100000, a real day at the counter: the program runs for 8 seconds and the online compiler stops it with Time Limit Exceeded. (On a fast machine it was still running after 12 seconds.)

Why searching a list is slow

  • Every enquiry starts at head and walks. On average it walks half the list: 500,000 steps.
  • 100,000 enquiries × 500,000 steps = 50 billion steps. In Big-O notation a list search is O(n): the work grows in step with the number of bookings.
  • The list is sorted, but that doesn't help: you can't jump to the middle of a list. You can only follow next.
  • Each check rules out exactly one booking. We need checks that rule out many bookings at once.

The idea: guess the number

Real-life example: "Guess my number, 1 to 100." You may ask "bigger or smaller?". Nobody asks "is it 1? is it 2?". You ask about 50; if the answer is "bigger", 1 to 50 are gone with one question. A dictionary works the same way: open it in the middle, see that your word comes later, and the whole first half is gone. Halving only works because the words are sorted.

Data size Questions when you halve
100 7 (100 → 50 → 25 → 12 → 6 → 3 → 1)
1,000 10
1,000,000 about 20
1,000,000,000 about 30

The number of halvings is log₂ n ("log base 2 of n"): how many times you can halve n before reaching 1. That's why it grows so slowly.

Where do we keep the middle?

Halving (fast search) Adding a new booking
Sorted array yes: the middle is a[n/2] (binary search, episode 25) slow: everything after it moves (episode 22's row of chairs)
Linked list no: there is no middle, only next fast: change two pointers
Binary search tree yes: every node is a middle fast: walk down and hang it on an empty spot

So we invent a structure with both: each node stands in the middle and keeps two pointers, left to the smaller bookings and right to the bigger bookings.

Building the tree by hand

Insert the bookings 50, 30, 70, 20, 40, 60, 80 one at a time. Each one starts at the top, compares, goes left (smaller) or right (bigger), and stops at the first empty spot:

              50            ← root
            /    \
          30      70
         /  \    /  \
        20  40  60   80     ← leaves
  • 50 arrives first: the tree is empty, so 50 is the top node, the root.
  • 30 < 50 → left. 70 > 50 → right.
  • 20 < 50 → left, 20 < 30 → left. 40, 60 and 80 find their places the same way.

Search for 60: 60 > 50 → go right (the whole left side is ruled out) · 60 < 70 → go left · found, in 3 steps. That's the guessing game, built into memory.

Tree words

Real-life example: a family tree. Dada ji at the top is the one everyone comes from; a father and his children are one level apart; the youngest kids have no children of their own; one uncle with his whole family is a complete family tree by itself. In computer science, trees are drawn upside down: the root at the top.

Family tree Tree in C In our picture
Dada ji at the top root: the top node 50
Father → his children parent → child: a node and the nodes it points to 30 is the parent of 20 and 40
The youngest kids, no children leaf: left and right are both NULL 20, 40, 60, 80
One uncle's whole family subtree: a child plus everything below it 70, 60, 80 is the right subtree of 50
Number of generations height: levels on the longest path from the root down 3
  • A tree is nodes linked from parent to child, starting at one root, with no loops. Every node except the root has exactly one parent.
  • A binary tree is a tree where every node has at most 2 children ("binary" = two).
  • A binary search tree (BST) is a binary tree with one more rule, for every node: everything in its left subtree is smaller, everything in its right subtree is bigger. That rule is what makes searching fast.
  • Search cost = the height of the tree, because each step goes one level down.

The node

Instead of one next pointer, two:

struct node {
    int pnr;
    struct node *left;
    struct node *right;
};

A node can't contain whole nodes (struct node left; gives error: field 'left' has incomplete type, the same as episode 22), so left and right are pointers. NULL means "no child here".

Insert, and your first recursion

Insert in plain words:

  1. If the tree is empty (root == NULL), the new node is the tree.
  2. If the new booking is smaller than the root, insert it into the left subtree.
  3. If it's bigger, insert it into the right subtree.

But a subtree is a tree. So "insert into the left subtree" is the same job on a smaller tree, and the insert function can simply call insert. A function that calls itself is called recursion. Every call goes one level down, so it eventually reaches an empty spot (step 1) and stops: that stopping case is the base case. Without a base case a recursive function never stops. (Episode 27 is all about recursion.)

The obvious attempt crashes

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

struct node {
    int pnr;
    struct node *left;
    struct node *right;
};

void insert(struct node *root, int pnr) {
    if (root == NULL) {
        root = malloc(sizeof(struct node));
        root->pnr = pnr;
        root->left = root->right = NULL;
        return;
    }
    if (pnr < root->pnr)
        insert(root->left, pnr);
    else
        insert(root->right, pnr);
}

int main() {
    struct node *root = NULL;
    insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    printf("Root: %d\n", root->pnr);
    return 0;
}
Segmentation fault

root in main is still NULL, so root->pnr crashes. The same trap as episode 22: C passes arguments by value. insert got a copy of root, stored the new node in its copy, and main never saw it. (The nodes are also leaked.)

The fix: return the root

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

struct node {
    int pnr;
    struct node *left;
    struct node *right;
};

struct node *insert(struct node *root, int pnr) {
    if (root == NULL) {
        struct node *n = malloc(sizeof(struct node));
        n->pnr = pnr;
        n->left = n->right = NULL;
        return n;
    }
    if (pnr < root->pnr)
        root->left = insert(root->left, pnr);
    else if (pnr > root->pnr)
        root->right = insert(root->right, pnr);
    return root;
}

int main() {
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    printf("Root: %d\n", root->pnr);
    printf("Left: %d, right: %d\n", root->left->pnr, root->right->pnr);
    return 0;
}
Root: 50
Left: 30, right: 70
  • For an empty tree, insert returns the new node, and the caller stores it.
  • Otherwise root->left = insert(root->left, pnr);: the left child becomes whatever inserting into the left subtree returns. If the left subtree was empty, that's the new node; if not, it's the same left child as before. Same on the right.
  • An equal booking number matches neither < nor >, so it's ignored: no duplicates.
  • main always writes root = insert(root, ...).

Search doesn't need recursion: start at the root and go down one level per step.

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

struct node {
    int pnr;
    struct node *left;
    struct node *right;
};

struct node *insert(struct node *root, int pnr) {
    if (root == NULL) {
        struct node *n = malloc(sizeof(struct node));
        n->pnr = pnr;
        n->left = n->right = NULL;
        return n;
    }
    if (pnr < root->pnr)
        root->left = insert(root->left, pnr);
    else if (pnr > root->pnr)
        root->right = insert(root->right, pnr);
    return root;
}

int search(struct node *root, int pnr) {
    int steps = 0;
    while (root != NULL) {
        steps++;
        if (pnr == root->pnr) {
            printf("%d: found, steps: %d\n", pnr, steps);
            return 1;
        }
        if (pnr < root->pnr)
            root = root->left;
        else
            root = root->right;
    }
    printf("%d: not found, steps: %d\n", pnr, steps);
    return 0;
}

int main() {
    int pnrs[] = {50, 30, 70, 20, 40, 60, 80};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++)
        root = insert(root, pnrs[i]);
    search(root, 60);
    search(root, 50);
    search(root, 65);
    return 0;
}
60: found, steps: 3
50: found, steps: 1
65: not found, steps: 3

65 is not found after 3 steps: 65 > 50 → right, 65 < 70 → left to 60, 65 > 60 → right, and 60's right is NULL. Falling off the tree into NULL means "not there".

In-order traversal: everything, sorted

Going through every node of a tree is called a traversal. Everything smaller than a node is in its left subtree, so to print in order: print the left subtree, then the node, then the right subtree. Left, me, right: the in-order traversal. An empty tree prints nothing (the base case).

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

struct node {
    int pnr;
    struct node *left;
    struct node *right;
};

struct node *insert(struct node *root, int pnr) {
    if (root == NULL) {
        struct node *n = malloc(sizeof(struct node));
        n->pnr = pnr;
        n->left = n->right = NULL;
        return n;
    }
    if (pnr < root->pnr)
        root->left = insert(root->left, pnr);
    else if (pnr > root->pnr)
        root->right = insert(root->right, pnr);
    return root;
}

void inorder(struct node *root) {
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->pnr);
    inorder(root->right);
}

int main() {
    int pnrs[] = {50, 70, 30, 60, 20, 80, 40};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++)
        root = insert(root, pnrs[i]);
    printf("Sorted: ");
    inorder(root);
    printf("\n");
    return 0;
}
Sorted: 20 30 40 50 60 70 80

The bookings were inserted in a mixed-up order (50, 70, 30, 60, 20, 80, 40), and in-order prints them sorted, for free.

Three ways to visit every node

Traversal Order Our tree prints Used for
In-order left, me, right 20 30 40 50 60 70 80 sorted output
Pre-order me, left, right 50 30 20 40 70 60 80 copying / saving a tree (insert in this order to rebuild the same shape)
Post-order left, right, me 20 40 30 60 80 70 50 freeing a tree (children before parents)

Same three lines of code; only where you visit the node moves. Each traversal visits every node once: O(n).

The big test: a million bookings

A million bookings in a random order (the shuffle loop swaps every booking with a random earlier one; this is the Fisher-Yates shuffle), inserted into the tree, then the same 100,000 random enquiries with a quiet search, and the tree's height, computed recursively as 1 + the taller of the two subtrees:

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

struct node {
    int pnr;
    struct node *left;
    struct node *right;
};

struct node *insert(struct node *root, int pnr) {
    if (root == NULL) {
        struct node *n = malloc(sizeof(struct node));
        n->pnr = pnr;
        n->left = n->right = NULL;
        return n;
    }
    if (pnr < root->pnr)
        root->left = insert(root->left, pnr);
    else if (pnr > root->pnr)
        root->right = insert(root->right, pnr);
    return root;
}

int search(struct node *root, int pnr) {
    while (root != NULL) {
        if (pnr == root->pnr)
            return 1;
        root = pnr < root->pnr ? root->left : root->right;
    }
    return 0;
}

int height(struct node *root) {
    if (root == NULL)
        return 0;
    int l = height(root->left), r = height(root->right);
    return 1 + (l > r ? l : r);
}

#define N 1000000
#define Q 100000
#define SHUFFLE 1

int main() {
    int *pnr = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++)
        pnr[i] = i + 1;
    for (int i = N - 1; i > 0 && SHUFFLE; i--) {
        int j = rand() % (i + 1);
        int t = pnr[i]; pnr[i] = pnr[j]; pnr[j] = t;
    }
    struct node *root = NULL;
    for (int i = 0; i < N; i++)
        root = insert(root, pnr[i]);
    int found = 0;
    for (int q = 0; q < Q; q++)
        found += search(root, rand() % N + 1);
    printf("Bookings: %d, enquiries: %d, found: %d\n", N, Q, found);
    printf("Height: %d\n", height(root));
    return 0;
}
Bookings: 1000000, enquiries: 100000, found: 100000
Height: 46

About one second in total (the compiler reported Time: 1.038s), and most of that is building the million nodes. The height is 46, so every enquiry takes at most 46 steps, against up to 1,000,000 for the list. (A perfectly balanced tree would need only 20 levels; a random tree is a bit taller but still tiny.)

int t = pnr[i]; pnr[i] = pnr[j]; pnr[j] = t; is the classic three-step swap with a temporary variable.

The sorted-input trap

Bookings are usually created in order: 1, 2, 3, ... Change #define SHUFFLE 1 to #define SHUFFLE 0 (the && SHUFFLE condition makes the shuffle loop stop at once) and run the same program: Time Limit Exceeded. It can't even finish building the tree.

Why? Every new booking is bigger than everything so far, so it always goes right:

1
 \
  2
   \
    3
     \
      4   ...   a "stick": height = number of nodes

The tree becomes a stick (a degenerate tree), which is just a linked list with extra pointers. Inserting booking k walks past k − 1 nodes, so a million inserts take about 500 billion steps. (The recursive insert would also go a million calls deep, which can overflow the stack.)

Shape Height for n nodes 1,000,000 bookings Search cost
Balanced (short and bushy) about log₂ n about 20 levels O(log n)
Random order a small multiple of log₂ n 46 in our run O(log n) on average
Degenerate (a stick) n 1,000,000 levels O(n), like a list

Fixes:

  1. Shuffle the input before inserting (what we did).
  2. Use a self-balancing tree: AVL trees and red-black trees rearrange (rotate) a few nodes after each insert so the height always stays about log₂ n. C++'s std::map and Java's TreeMap are red-black trees.

Freeing a tree

Every malloc needs a free. Free the left subtree, free the right subtree, and only then the node itself: post-order.

void free_tree(struct node *root) {
    if (root == NULL)
        return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

If you freed the parent first, you could no longer read its left and right pointers: the children would be lost (a leak), or read after free (undefined behaviour).

Mini project: a phone book

Your phone's contact list as a BST. The key is now a name, so the comparison is strcmp (episode 9): negative means the name comes first in the alphabet → go left; positive → go right; zero → the same name, so update the number.

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

struct contact {
    char name[20];
    char phone[12];
    struct contact *left, *right;
};

struct contact *add(struct contact *root, char *name, char *phone) {
    if (root == NULL) {
        struct contact *c = malloc(sizeof(struct contact));
        strcpy(c->name, name);
        strcpy(c->phone, phone);
        c->left = c->right = NULL;
        return c;
    }
    int cmp = strcmp(name, root->name);
    if (cmp < 0)
        root->left = add(root->left, name, phone);
    else if (cmp > 0)
        root->right = add(root->right, name, phone);
    else
        strcpy(root->phone, phone);   // same name: new number
    return root;
}

struct contact *find(struct contact *root, char *name) {
    while (root != NULL) {
        int cmp = strcmp(name, root->name);
        if (cmp == 0)
            return root;
        root = cmp < 0 ? root->left : root->right;
    }
    return NULL;
}

void print_all(struct contact *root) {
    if (root == NULL)
        return;
    print_all(root->left);
    printf("%-6s %s\n", root->name, root->phone);
    print_all(root->right);
}

void free_tree(struct contact *root) {
    if (root == NULL)
        return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main() {
    struct contact *book = NULL;
    book = add(book, "Meera", "9876500001");
    book = add(book, "Arjun", "9876500002");
    book = add(book, "Zoya", "9876500003");
    book = add(book, "Kabir", "9876500004");
    book = add(book, "Arjun", "9876500099");
    print_all(book);
    struct contact *c = find(book, "Kabir");
    if (c != NULL)
        printf("Kabir: %s\n", c->phone);
    if (find(book, "Rohan") == NULL)
        printf("Rohan: not in contacts\n");
    free_tree(book);
    return 0;
}
Arjun  9876500099
Kabir  9876500004
Meera  9876500001
Zoya   9876500003
Kabir: 9876500004
Rohan: not in contacts
  • print_all is an in-order traversal, so the contacts come out alphabetically, though they were added in a different order.
  • Adding Arjun again updated his number instead of making a duplicate.
  • find returns a pointer to the contact, or NULL if the name isn't there.
  • %-6s prints the name left-aligned in 6 characters, so the numbers line up.
  • free_tree is post-order; AddressSanitizer (gcc -g -fsanitize=address) reports no leaks and no errors for this program.

Your turn: add int count(struct contact *root). Hint: one, plus the count of the left subtree, plus the count of the right subtree.

Common mistakes (and the real messages)

Mistake What you see Why Fix
struct node left; inside struct node error: field 'left' has incomplete type A node can't contain whole nodes struct node *left;
void insert(struct node *root, ...) { root = malloc(...); } Segmentation fault when main uses root insert changed a copy; main's root is still NULL root = insert(root, ...), returning the root
insert(root->left, pnr); (result not stored) No error: only the root survives (Sorted: 50) The returned subtree is thrown away root->left = insert(root->left, pnr);
A recursive function with no if (root == NULL) return; Segmentation fault It reads NULL->left Always handle the empty tree first: the base case
root->left->pnr when root->left is NULL Segmentation fault There is no left child Check for NULL before following a pointer
Inserting sorted data Time Limit Exceeded The tree becomes a stick Shuffle first, or use a balanced tree
Freeing the parent before its children Leak, or use after free The child pointers live inside the parent Post-order: children first
Comparing string keys with < or == Wrong order / never found Compares addresses, not text strcmp(a, b) < 0, == 0

The lost-subtrees bug, run in the online compiler (the insert from above, with the two assignments removed):

    if (pnr < root->pnr)
        insert(root->left, pnr);
    else if (pnr > root->pnr)
        insert(root->right, pnr);
    return root;
Sorted: 50

Practice

  1. Write int count(struct node *root) that returns the number of nodes.
  2. Write smallest and largest. (Hint: the smallest booking is as far left as you can go.)
  3. Write preorder and check it prints 50 30 20 40 70 60 80 for our tree.
  4. Insert 1 to 10 in order and print the height. What shape is the tree?
  5. (Interview classic) Write struct node *delete_pnr(struct node *root, int pnr) that removes a booking. Think about three cases: a leaf, a node with one child, a node with two children.
Solutions

All five, verified together (uses insert, inorder and height from above):

int count(struct node *root) {
    if (root == NULL)
        return 0;
    return 1 + count(root->left) + count(root->right);
}

int smallest(struct node *root) {      // assumes the tree is not empty
    while (root->left != NULL)
        root = root->left;
    return root->pnr;
}

int largest(struct node *root) {       // assumes the tree is not empty
    while (root->right != NULL)
        root = root->right;
    return root->pnr;
}

void preorder(struct node *root) {
    if (root == NULL)
        return;
    printf("%d ", root->pnr);
    preorder(root->left);
    preorder(root->right);
}

struct node *delete_pnr(struct node *root, int pnr) {
    if (root == NULL)
        return NULL;                         // not found: nothing to do
    if (pnr < root->pnr)
        root->left = delete_pnr(root->left, pnr);
    else if (pnr > root->pnr)
        root->right = delete_pnr(root->right, pnr);
    else if (root->left == NULL) {           // 0 or 1 child (right)
        struct node *r = root->right;
        free(root);
        return r;
    } else if (root->right == NULL) {        // 1 child (left)
        struct node *l = root->left;
        free(root);
        return l;
    } else {                                 // 2 children
        int next = smallest(root->right);    // the next bigger booking
        root->pnr = next;
        root->right = delete_pnr(root->right, next);
    }
    return root;
}

void free_tree(struct node *root) {
    if (root == NULL)
        return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main() {
    int pnrs[] = {50, 30, 70, 20, 40, 60, 80};
    struct node *root = NULL;
    for (int i = 0; i < 7; i++)
        root = insert(root, pnrs[i]);
    printf("Count: %d\n", count(root));
    printf("Smallest: %d, largest: %d\n", smallest(root), largest(root));
    printf("Pre-order: ");
    preorder(root);
    printf("\n");
    root = delete_pnr(root, 20);    // a leaf
    root = delete_pnr(root, 70);    // two children
    root = delete_pnr(root, 50);    // the root
    printf("After deleting 20, 70, 50: ");
    inorder(root);
    printf("\nNew root: %d\n", root->pnr);

    struct node *stick = NULL;
    for (int k = 1; k <= 10; k++)
        stick = insert(stick, k);
    printf("Inserted 1..10 in order, height: %d\n", height(stick));
    free_tree(root);
    free_tree(stick);
    return 0;
}
Count: 7
Smallest: 20, largest: 80
Pre-order: 50 30 20 40 70 60 80 
After deleting 20, 70, 50: 30 40 60 80 
New root: 60
Inserted 1..10 in order, height: 10
  • 4. Height 10: every node went right, a stick.
  • 5. Deleting a node with two children: replace its value with the next bigger value (the smallest node of its right subtree, called the in-order successor), then delete that node from the right subtree. It has no left child, so it's an easy case. Deleting 70 copies 80 into its place; deleting 50 copies 60 into the root. (We avoid naming the function delete: that's a keyword in C++, and remove is already a function in <stdio.h>.) AddressSanitizer reports no errors for this program.

Quick quiz

root = insert(NULL, 5);
root = insert(root, 3);
root = insert(root, 8);
root = insert(root, 4);
printf("%d", root->left->right->pnr);
  • A. 3
  • B. 4
  • C. 8
  • D. Segmentation fault
Answer

B: 4. 3 < 5 goes left of 5; 8 > 5 goes right; 4 < 5 goes left to 3, then 4 > 3 goes right. So root->left is 3 and root->left->right is 4.

Interview questions

  • What is a binary tree? What is a binary search tree, and what is the BST property?
  • Define root, leaf, parent, child, subtree, height and depth.
  • What are the time complexities of search, insert and delete in a BST? (O(height): O(log n) when balanced, O(n) in the worst case.)
  • When does a BST degenerate into a linked list? How do AVL and red-black trees prevent it?
  • Write in-order, pre-order and post-order traversals. Which one prints a BST in sorted order? Which one would you use to free a tree, and why?
  • Why must a recursive insert return the root (or take a struct node **)?
  • How do you delete a node with two children from a BST?
  • How do you find the minimum and maximum in a BST?
  • How would you check whether a binary tree is a valid BST? (Pass down a min and max allowed value; checking only each node's direct children is not enough.)
  • Level-order traversal: how would you print a tree level by level? (Use a queue: episode 23.)
  • BST vs sorted array vs hash table: when would you choose each?

Glossary

Term Meaning Example
Tree Nodes linked from parent to child, starting at one root, with no loops the bookings tree
Node One element of the tree: data plus pointers to its children struct node { int pnr; struct node *left; struct node *right; };
Root The top node, where every search starts 50
Parent / child A node and the nodes it points to 30 is the parent of 20 and 40
Leaf A node with no children: left and right are both NULL 20, 40, 60, 80
Subtree A child plus everything below it; itself a tree 70, 60, 80
Height The number of levels on the longest path from the root down 3 for our 7-node tree
Depth (level) How many steps a node is below the root 60 is at depth 2
Binary tree A tree where every node has at most 2 children left and right
Binary search tree (BST) A binary tree where every left subtree is smaller and every right subtree is bigger our bookings tree
Balanced tree A tree whose height stays about log₂ n a million nodes in ~20 levels
Degenerate tree (stick) A tree where every node has one child: effectively a list 1, 2, 3, 4 inserted in order
Self-balancing tree A BST that rearranges nodes after inserts to stay balanced AVL tree, red-black tree
Recursion A function that calls itself on a smaller part of the problem insert calls insert on a subtree
Base case The case where a recursive function stops without calling itself if (root == NULL)
Traversal Visiting every node of a structure once in-order, pre-order, post-order
In-order Left, me, right: prints a BST sorted 20 30 40 50 60 70 80
Pre-order Me, left, right: parents before children 50 30 20 40 70 60 80
Post-order Left, right, me: children before parents used by free_tree
Linear search Checking items one by one from the start searching the linked list
log₂ n How many times you can halve n before reaching 1 log₂ 1,000,000 ≈ 20
Big-O How the work grows with the input size n list search O(n), balanced BST search O(log n)
Shuffle (Fisher-Yates) Putting an array in random order by swapping each item with a random earlier one the SHUFFLE loop
rand() Returns a pseudo-random int from <stdlib.h> rand() % N + 1
strcmp Compares two strings: negative, zero or positive strcmp("Arjun", "Meera") < 0
Segmentation fault The program read or wrote memory it doesn't own, often through NULL root->pnr with root == NULL
Time Limit Exceeded The online compiler stopped a program that ran longer than 8 seconds 100,000 list searches

Summary

  • Searching a linked list means walking it: O(n) per search. 100,000 searches in a million bookings hit Time Limit Exceeded, and sorting the list doesn't help.
  • Halving (the guessing game, the dictionary) needs a way to reach "the middle". A binary search tree builds that in: each node has left (smaller) and right (bigger).
  • Tree words: root, parent, child, leaf, subtree, height; a binary tree has at most two children per node; a BST adds the smaller-left, bigger-right rule.
  • insert is recursive (the same job on a smaller tree, stopping at the base case, an empty tree) and must return the root: root = insert(root, x) and root->left = insert(root->left, x).
  • Search goes down one level per step: cost = the height. A million random bookings gave height 46, and 100,000 searches took about a second.
  • In-order (left, me, right) prints a BST sorted; pre-order copies it; post-order frees it.
  • Sorted input turns a plain BST into a stick (as slow as a list): shuffle, or use a self-balancing tree (AVL, red-black).
  • The same tree works for any key you can compare: names with strcmp make a phone book.

Next episode: Sorting and searching in C: putting a whole array in order, and binary search, the guessing game on an array.