Binary trees

Lesson

A binary tree has nodes with up to two children (left, right). A binary search tree additionally maintains: left subtree values < node value < right subtree values. That invariant lets you find, insert, or delete in O(log n) — if the tree stays balanced.

For real use, prefer self-balancing variants (red-black, AVL) or libraries — a hand-rolled BST degenerates to a linked list on sorted input.

Code examples

typedef struct bst { int v; struct bst *l, *r; } bst_t;
bst_t *bst_insert(bst_t *r, int v) {
    if (!r) { bst_t *n = malloc(sizeof *n); n->v=v; n->l=n->r=NULL; return n; }
    if (v < r->v) r->l = bst_insert(r->l, v);
    else if (v > r->v) r->r = bst_insert(r->r, v);
    return r;
}

Common mistakes

• Forgetting to reassign r->l = bst_insert(r->l, v) — the new node never attaches.