Binary Trees and BSTs

This chapter implements binary trees and binary search trees (BSTs), the foundation for ordered, hierarchical data.

Why This Matters

Binary trees model hierarchical relationships and are the basis for balanced trees, heaps, tries, and expression trees. BSTs provide ordered traversal and O(log n) average search/insert/delete.

Prerequisites

• c.ds.1 — foundations.

Core Concept

A binary tree is a node with up to two children (left, right):

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

A binary search tree (BST) adds an ordering invariant: for every node, left-subtree values < node value < right-subtree values. This enables O(log n) search on a balanced tree.

Examples

BST insert

Node *bst_insert(Node *root, int value)
{
    if (root == NULL) {
        Node *n = malloc(sizeof *n);
        if (!n) return NULL;
        n->value = value;
        n->left = n->right = NULL;
        return n;
    }
    if (value < root->value)
        root->left = bst_insert(root->left, value);
    else if (value > root->value)
        root->right = bst_insert(root->right, value);
    return root;
}

In-order traversal (sorted order)

void inorder(Node *root)
{
    if (!root) return;
    inorder(root->left);
    /* visit root->value */
    inorder(root->right);
}

In-order traversal of a BST yields values in sorted order.

How It Works

Search follows the ordering invariant: go left if the target is smaller, right if larger. Insert and delete preserve the invariant. On a balanced tree, each step halves the remaining subtree, giving O(log n).

Variations

Balanced trees

A plain BST degenerates to O(n) if values are inserted in sorted order. Self-balancing trees (AVL, red-black — c.ds.7) maintain O(log n) worst case.

Non-search trees

Not every binary tree is a BST. Expression trees, Huffman trees, and heaps have different invariants.

Common Mistakes

• Forgetting the base case (NULL) in recursive insert/search.
• Losing the root when inserting without returning/updating it.
• Not freeing nodes (leaks).
• Ignoring the degenerate (sorted-insert) case.

Undefined Behavior

• Dereferencing a NULL child. VERIFIED
• Use-after-free during deletion. VERIFIED

Portability

• Plain C, fully portable.

Under the Hood

A BST is a pointer-based structure; traversal follows pointers and has poor cache locality compared to an array. Balanced trees add rotation overhead to maintain depth.

Practical Usage

• Use BSTs for ordered maps/sets when the data is not adversarial and

balance is acceptable.

• Use balanced trees (c.ds.7) when worst-case O(log n) is required.
• Use binary trees for expression ASTs and recursive structures.

Exercises

1. Implement bst_search, bst_insert, bst_min, and bst_delete. 2. Implement inorder and confirm sorted output. 3. Implement bst_height and bst_size. 4. Show that inserting sorted values degenerates the tree to O(n).

Deep Challenge

Implement iterative (non-recursive) in-order traversal using an explicit stack, and explain why it avoids stack overflow for very deep trees where recursion fails.

Related Concepts

• c.ds.7 — balanced trees.
• c.ds.8 — heaps.
• c.core.18 — recursion.

References

• Standard data-structure literature.

Verification

• BST invariants and traversal semantics. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Binary tree
• [ ] BST invariant
• [ ] Insert/search/delete
• [ ] In-order traversal

Mastery levels