Binary trees

Overview

A binary tree is one of the most useful data structures in programming. Instead of laying values out in a straight line like an array or a linked list, a tree organizes them in a branching, hierarchical shape: each piece of data lives in a node, and each node points to up to two other nodes below it. That branching shape is what makes trees fast to search.

You already know two ideas this lesson builds on. From Structs you know how to bundle related data into one type. From Linked lists you know how to connect nodes with pointers and walk from one to the next. A binary tree is the natural next step: instead of a single next pointer, each node has two pointers — usually called left and right. A linked list is, in a sense, a tree where every node has only one child.

The most common kind of binary tree is the binary search tree (BST). A BST adds an ordering rule so that finding a value becomes a series of yes/no decisions ("go left or go right?") rather than a scan of every element. When the tree is reasonably balanced, each decision throws away half the remaining nodes, giving roughly O(log n) lookups.

Trees are everywhere in real software: file-system directories, the parse trees compilers build, database indexes, decision logic in games and AI, and the auto-complete structures behind search boxes. Understanding the plain binary tree here is the foundation for all of them.

Key terms used throughout: a node holds a value and child pointers; the root is the topmost node; a leaf is a node with no children; the height is the number of nodes on the longest path from root to a leaf; and a subtree is any node together with everything beneath it.

Why it matters

Trees turn slow linear searches into fast logarithmic ones, and that difference shows up constantly in real systems:

• Databases use B-trees and B+-trees (generalizations of binary trees) for indexes so a query can find one row among millions without scanning the whole table.
• File systems model directories as trees; every path you type walks down one.
• Compilers and interpreters parse source code into an abstract syntax tree (AST) and walk it to generate output.
• Standard libraries implement ordered maps and sets (for example, C++'s std::map, Java's TreeMap) as balanced binary search trees, so you get sorted iteration and fast lookup for free.

From a robustness standpoint, trees are also a classic place where pointer mistakes cause crashes: a forgotten reassignment silently drops nodes, and a sloppy free routine causes use-after-free or leaks. Learning to build, traverse, and tear down a tree correctly trains exactly the careful pointer discipline that production C demands.

Core concepts

1. The node and its two pointers

Definition. A binary-tree node is a struct that stores a value plus two pointers to nodes of the same type — left and right. A NULL pointer means "no child here."

typedef struct tnode {
    int v;                 /* the value stored in this node */
    struct tnode *l, *r;   /* left child, right child (NULL = none) */
} tnode_t;

Notice the struct refers to itself through pointers (struct tnode *). This is the same self-referential trick used in Linked lists, just with two links instead of one. The whole tree is represented by a single pointer to its root; NULL represents an empty tree.

         (8)            <- root
        /   \
      (3)   (10)
      / \      \
    (1) (6)    (14)     <- 14 is a leaf, so are 1 and 6

When to use a tree vs. a list/array. Use a tree when you need fast ordered lookup and the data changes (insert/delete) often. Use an array when data is fixed and you want cache-friendly scans; use a linked list when you only ever step front-to-back.

Pitfall. Beginners forget to set both child pointers to NULL when creating a node. An uninitialized pointer holds garbage, and the first traversal will dereference it and crash.

Knowledge check: In the diagram above, which nodes are leaves, and what is the height of the tree (count nodes on the longest root-to-leaf path)?

2. The binary search tree (BST) invariant

Definition. A BST is a binary tree with an ordering rule that must hold at every node: every value in the left subtree is less than the node's value, and every value in the right subtree is greater than it. (This lesson treats duplicates as ignored.)

An invariant is a condition you promise to keep true before and after every operation. Insert and delete must each preserve it.

              node = 8
          /            \
  all values < 8     all values > 8
  { 1, 3, 6 }        { 10, 14 }

How searching works internally. To find a value, start at the root and compare. If the target is smaller, go left; if larger, go right; if equal, you found it. Each comparison discards one whole subtree. In a balanced tree that halves the search space each step, giving O(log n). In an unbalanced tree it can be O(n) (see concept 4) — that is exactly what the quiz asks.

When NOT to use a BST. If you never search by key and only need ordering, an array + sort may be simpler. If you need guaranteed O(log n) under any input, a plain BST is not enough — use a self-balancing tree.

Pitfall. Confusing the local rule (only compare with the immediate parent) with the global invariant (the rule must hold for the whole subtree, not just the direct child). A node can satisfy its parent yet violate an ancestor.

Knowledge check: Is the following a valid BST? Root 8, left child 3, and 3's right child is 9. Explain why or why not.

3. Traversals: pre-order, in-order, post-order

Definition. A traversal is a systematic visit of every node exactly once. The three depth-first orders differ only in when you process the current node relative to its children.

For the tree above (root 8):
in-order  -> 1 3 6 8 10 14   (sorted!)
pre-order -> 8 3 1 6 10 14
post-order-> 1 6 3 14 10 8

How it works internally. Each traversal is naturally recursive: handle the left subtree, the node, and the right subtree in some order. The call stack remembers where to return. Recursion depth equals the tree's height, which matters for deep trees (concept 4).

When to use which. In-order to read sorted data; post-order to destroy a tree (children before parent); pre-order to rebuild or clone.

Pitfall. Freeing in pre-order or in-order: if you free(node) before recursing into its children, the child pointers are gone (dangling) and you crash or leak. Always free in post-order.

Knowledge check: Predict the in-order output for a BST built by inserting 5, 2, 8, 1, 3 in that order.

4. Balance and complexity

Definition. A tree is balanced when the left and right sides stay roughly equal in height, so height stays near log2(n). It is degenerate when nodes line up along one side, making height grow to n.

Balanced (n=7, height 3)      Degenerate (n=4, height 4)
        4                          1
       / \                          \
      2   6                          2
     / \ / \                          \
    1  3 5  7                          3
                                        \
                                         4   (acts like a linked list)

Why it matters. A hand-written BST has no balancing logic. If you insert already-sorted input (1, 2, 3, 4, ...), every new value goes to the right, and the tree collapses into a chain. Lookups then cost O(n) — the worst case the quiz refers to. For production, use a self-balancing variant (AVL or red-black tree) or a tested library that maintains balance automatically.

Pitfall. Benchmarking a plain BST on random data, concluding it is O(log n), and then feeding it sorted real-world data that quietly degrades to O(n).

Syntax notes

The core pieces are the node type, a node allocator, recursive insert, and recursive traversal. Here is the shape with comments on the non-obvious lines.

#include <stdlib.h>

typedef struct tnode {
    int v;
    struct tnode *l, *r;
} tnode_t;

/* Allocate one node; returns NULL on allocation failure. */
tnode_t *node_new(int v) {
    tnode_t *n = malloc(sizeof *n);   /* sizeof *n = size of one tnode_t */
    if (!n) return NULL;              /* always check malloc */
    n->v = v;
    n->l = n->r = NULL;              /* a fresh node has no children */
    return n;
}

/* Insert v; return the (possibly new) subtree root. */
tnode_t *insert(tnode_t *root, int v) {
    if (!root) return node_new(v);    /* empty spot -> create here */
    if (v < root->v)
        root->l = insert(root->l, v); /* reassign the child pointer! */
    else if (v > root->v)
        root->r = insert(root->r, v);
    /* v == root->v: duplicate, ignore */
    return root;                       /* unchanged root flows back up */
}

The critical idiom is root->l = insert(root->l, v);. Insert returns the subtree root, and the caller stores it back. That single line is what attaches a new node to its parent.

Lesson

What is a binary tree?

A binary tree is made of nodes. Each node can have up to two children, called left and right.

What makes it a search tree?

A binary search tree (BST) adds one rule, called an invariant (a condition that must always hold):

• All values in the left subtree are less than the node's value.
• All values in the right subtree are greater than the node's value.

This ordering lets you find, insert, or delete a value in O(log n) time — as long as the tree stays balanced. "Balanced" means the left and right sides stay roughly equal in height.

A warning about balance

A hand-written BST has a weakness: if you insert already-sorted input, every value goes to one side. The tree turns into a long chain — effectively a linked list — and lookups slow down to O(n).

For real-world use, prefer a self-balancing variant (such as red-black or AVL trees) or a tested library.

Code examples

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

typedef struct tnode {
    int v;
    struct tnode *l, *r;
} tnode_t;

/* Create a single node with no children. NULL on out-of-memory. */
static tnode_t *node_new(int v) {
    tnode_t *n = malloc(sizeof *n);
    if (!n) return NULL;
    n->v = v;
    n->l = n->r = NULL;
    return n;
}

/* Insert v keeping the BST invariant. Returns the subtree root. */
static tnode_t *insert(tnode_t *root, int v) {
    if (!root) return node_new(v);
    if (v < root->v)        root->l = insert(root->l, v);
    else if (v > root->v)   root->r = insert(root->r, v);
    /* equal -> duplicate, ignored */
    return root;
}

/* In-order traversal: prints a BST in ascending order. */
static void inorder(const tnode_t *root) {
    if (!root) return;
    inorder(root->l);
    printf("%d ", root->v);
    inorder(root->r);
}

/* Search: 1 if found, 0 otherwise. */
static int contains(const tnode_t *root, int v) {
    while (root) {
        if (v == root->v) return 1;
        root = (v < root->v) ? root->l : root->r;
    }
    return 0;
}

/* Post-order free: children before parent, so no dangling pointers. */
static void free_tree(tnode_t *root) {
    if (!root) return;
    free_tree(root->l);
    free_tree(root->r);
    free(root);
}

int main(void) {
    int vals[] = {8, 3, 10, 1, 6, 14};
    size_t n = sizeof vals / sizeof vals[0];

    tnode_t *root = NULL;
    for (size_t i = 0; i < n; i++) {
        tnode_t *updated = insert(root, vals[i]);
        if (!updated) {                 /* allocation failed */
            fprintf(stderr, "out of memory\n");
            free_tree(root);
            return 1;
        }
        root = updated;                  /* keep root current */
    }

    printf("sorted: ");
    inorder(root);
    putchar('\n');

    printf("contains 6?  %s\n", contains(root, 6) ? "yes" : "no");
    printf("contains 7?  %s\n", contains(root, 7) ? "yes" : "no");

    free_tree(root);   /* release every node */
    return 0;
}

What it does. It builds a BST from {8, 3, 10, 1, 6, 14}, prints the values in sorted order via an in-order traversal, searches for two keys, and frees the whole tree.

Expected output:

sorted: 1 3 6 8 10 14 
contains 6?  yes
contains 7?  no

Edge cases. An empty tree (root == NULL) is handled everywhere by the leading if (!root) guards. Duplicate inserts are ignored. malloc failure is checked, and on failure the partially built tree is freed before exiting so nothing leaks.

Line by line

We trace the build and the in-order print.

Building the tree — root starts at NULL, then we insert each value:

Resulting shape:

         (8)
        /   \
      (3)   (10)
      / \      \
    (1) (6)    (14)

In-order traversal of the root (8). inorder does left, then self, then right. Following the recursion:

1. inorder(8) calls inorder(3) first.
2. inorder(3) calls inorder(1); node 1 has no left, so it prints 1, then has no right -> returns.
3. Back in inorder(3): print 3, then inorder(6) prints 6.
4. Back in inorder(8): print 8.
5. inorder(10): no left, print 10, then inorder(14) prints 14.

Output order: 1 3 6 8 10 14 — sorted, because in-order always visits everything smaller (left subtree) before the node and everything larger (right subtree) after it.

Why root = updated; matters. The very first insert (8) creates the root and returns it; if we did not store the return value, root would stay NULL and the tree would never exist. For later inserts the root is unchanged, but the inner root->l = insert(...) lines are what wire each new node to its parent.

Common mistakes

Mistake 1 — Discarding the return value of insert.

/* WRONG */
insert(root->l, v);        /* result thrown away */

If root->l was NULL, insert creates a node and returns it, but nothing stores it, so the node is never attached (and leaks). Fix: always reassign.

/* CORRECT */
root->l = insert(root->l, v);

How to recognize it: values "disappear" — you insert them but searches and traversals never find them.

Mistake 2 — Forgetting to set children to NULL.

/* WRONG */
tnode_t *n = malloc(sizeof *n);
n->v = v;                   /* l and r still hold garbage */
return n;

The first traversal dereferences a garbage pointer and crashes. Fix: n->l = n->r = NULL; right after allocation.

Mistake 3 — Freeing in the wrong order.

/* WRONG */
free(root);
free_tree(root->l);         /* root is already freed: use-after-free */

Fix: recurse into both children first, then free the node (post-order). See free_tree in the example.

Mistake 4 — Not checking malloc.

Ignoring a NULL return from malloc means the next n->v = v; writes through a null pointer. Fix: check every allocation and handle failure gracefully (free what you built, report, exit).

Mistake 5 — Assuming the tree is balanced.

Inserting sorted data into a plain BST makes it a chain. Fix: shuffle inputs if you can, or use a self-balancing tree/library when O(log n) must be guaranteed.

Debugging tips

Compiler errors

• "dereferencing pointer to incomplete type" — you wrote struct tnode fields before the struct is fully declared, or used the typedef name inside the struct body. Inside the struct use struct tnode *l;, not tnode_t *l;.
• Implicit declaration of malloc/free — include <stdlib.h>.

Runtime errors (crashes)

• Segfault on the first traversal usually means uninitialized child pointers — confirm node_new sets l and r to NULL.
• Crash during free almost always means freeing a parent before its children — verify post-order in free_tree.
• Run under a memory checker: gcc -g -fsanitize=address,undefined tree.c && ./a.out catches use-after-free, leaks, and out-of-bounds immediately. valgrind ./a.out reports leaks and invalid reads/writes.

Logic errors

• In-order output not sorted? Your insert is putting values on the wrong side — re-check < vs > and that you compare against root->v.
• Some inserted values missing? You probably dropped the return value of insert (Mistake 1), or your duplicate handling silently swallows them.

Questions to ask when it doesn't work

1. After each insert, does root still point at a real node (not NULL)?
2. Are both child pointers NULL at creation?
3. Does in-order print exactly as many numbers as I inserted?
4. Does the sanitizer or Valgrind report any leak or invalid access?

Memory safety

Binary trees are heap-allocated and pointer-heavy, so they touch most of C's classic hazards:

• Initialization. Every new node must have v, l, and r set before use. Uninitialized l/r are the number-one cause of tree segfaults.
• NULL checks. Treat malloc as able to fail. After every allocation, check for NULL before writing fields. Every recursive function here also guards if (!root) return; so a NULL subtree is safe.
• Lifetimes / use-after-free. Free strictly in post-order (children before parent). After free_tree, the caller's root is dangling — do not touch it; set it to NULL if it will be reused.
• No double free. Each node is freed exactly once because the recursion visits each node once. Do not also free a node from somewhere else.
• Leaks. Every successful insert allocates one node; every node must reach free_tree. On an early error path (like the out-of-memory branch in main), free what was already built before returning.
• Stack depth / overflow. Recursion depth equals tree height. A degenerate tree of n nodes recurses n deep and can overflow the call stack for large n; balanced trees keep depth at ~log2(n). For very large or untrusted inputs, prefer an iterative traversal with an explicit stack, or a balanced structure.
• Integer concerns. Sums of node values can overflow int; accumulate into a wider type such as long (the companion exercise tree_sum returns long for exactly this reason).

Real-world uses

Concrete uses.

• Database indexes use B-trees/B+-trees (multi-way relatives of binary trees) so a WHERE id = ... lookup is logarithmic, not a full table scan.
• Ordered containers in standard libraries — C++ std::map/std::set, Java TreeMap/TreeSet — are red-black trees, giving sorted iteration plus O(log n) operations.
• Compilers parse code into an abstract syntax tree and traverse it (often post-order) to emit machine code or bytecode.
• File systems and UI model directory hierarchies and view hierarchies as trees.
• Routing, autocomplete, and spell-check use tree variants (tries, suffix trees) built on the same node-and-pointer idea.

Professional best-practice habits.

Beginner rules:

• Always initialize child pointers to NULL and check malloc.
• Pair every tree creation with a free_tree and run the result under AddressSanitizer/Valgrind.
• Give functions clear names (insert, contains, inorder, free_tree) and keep one responsibility each.
• Mark read-only traversals with const tnode_t * to document intent and catch accidental writes.

Advanced rules:

• For guaranteed O(log n) on any input, use a self-balancing tree (AVL, red-black) or a proven library rather than a hand-rolled BST.
• Prefer iterative traversal with an explicit stack when inputs can be huge or adversarial, to avoid call-stack overflow.
• Separate the value/key from the node mechanics (e.g., store a comparison function) so the tree can be reused for many types.
• Consider cache-friendlier structures (B-trees, sorted arrays) when data is read-heavy and rarely changes.

Practice tasks

Beginner 1 — Count the nodes.

• Objective: write int count(const tnode_t *root) returning the number of nodes.
• Requirements: recursive; empty tree returns 0.
• Example: the tree {8,3,10,1,6,14} returns 6.
• Hint: 1 + count(left) + count(right), with if (!root) return 0;.
• Concepts: recursion, NULL base case.

Beginner 2 — Find the minimum.

• Objective: write int tree_min(const tnode_t *root) returning the smallest value in a non-empty BST.
• Requirements: assume root is non-NULL; do it without a full traversal.
• Example: for {8,3,10,1,6,14} returns 1.
• Hint: in a BST the minimum is the left-most node — keep following ->l until it is NULL.
• Concepts: BST invariant, iteration.

Intermediate 1 — Search returning the node.

• Objective: write tnode_t *find(tnode_t *root, int v) returning the matching node or NULL.
• Requirements: iterative (a while loop), O(height).
• Example: find(root, 6) returns the node holding 6; find(root, 7) returns NULL.
• Hint: compare and move left or right; stop when found or NULL.
• Concepts: BST search, pointer movement.

Intermediate 2 — Pre-order and post-order printers.

• Objective: write preorder and postorder printing functions.
• Requirements: match the orders in the lesson; use const.
• Example: for {8,3,10,1,6,14}, pre-order prints 8 3 1 6 10 14 and post-order prints 1 6 3 14 10 8.
• Hint: same three calls as in-order, reordered.
• Concepts: traversal orders, recursion.

Challenge — Validate a BST.

• Objective: write int is_bst(const tnode_t *root) returning 1 if the tree obeys the BST invariant globally, else 0.
• Requirements: must catch a node that is fine versus its parent but violates an ancestor (the concept-2 pitfall). Handle the empty tree (return 1).
• Example: a tree where 8's left child 3 has a right child 9 must return 0 (9 belongs in 8's right subtree).
• Constraints: O(n) time; do not collect all values into an array if you can avoid it.
• Hint: pass down an allowed (min, max) range and tighten it as you descend (use the widest sentinels for the root).
• Concepts: invariants, recursion with extra parameters.

Summary

• A binary tree is built from nodes, each with a value and two child pointers, left and right; NULL means no child and an empty tree is just a NULL root.
• A binary search tree adds an invariant: left subtree < node < right subtree. That ordering makes search, insert, and delete O(log n) when balanced.
• The essential insert idiom is root->l = insert(root->l, v); — insert returns the subtree root and the caller stores it back. Forgetting this drops nodes.
• Three traversals matter: in-order prints a BST sorted, post-order is the safe order to free a tree, pre-order is good for cloning/serializing.
• Common mistakes: discarding insert's return value, uninitialized child pointers, freeing parents before children, ignoring malloc failure, and assuming balance.
• Remember: initialize children to NULL, check every allocation, free in post-order, test under AddressSanitizer/Valgrind, and reach for a self-balancing tree or library when sorted/untrusted input could turn your BST into an O(n) chain.

Practice with these exercises

• Height of a binary tree
• Sum of a binary tree