bst-library

A generic binary-search tree in C11.

Week 4 capstone · 14 June 2026 · 4 min read

A binary search tree is the simplest dynamic data structure that isn't a list. The library implements a generic one: it stores void* payloads, takes a user-supplied comparator, and never calls malloc on its own. The caller provides the allocator; the library provides the tree.

The API

Six functions cover the whole surface. The public header is short enough to read in one sitting:

typedef int   (*bst_cmp_fn)(const void *a, const void *b);
typedef void  (*bst_free_fn)(void *);

typedef struct bst bst;

bst  *bst_create   (bst_cmp_fn cmp, bst_free_fn free_key);
void  bst_destroy  (bst *t, bst_free_fn free_key,
                                bst_free_fn free_payload);
int   bst_insert   (bst *t, const void *key, void *payload);
void *bst_find     (const bst *t, const void *key);
int   bst_remove   (bst *t, const void *key);
void  bst_inorder  (const bst *t, bst_visit_fn visit, void *ctx);

size_t bst_size   (const bst *t);
size_t bst_height (const bst *t);
int    bst_empty  (const bst *t);

The tree is unbalanced — insertion order determines shape, and a sorted input produces a degenerate O(n) tree. A future version may add an AVL or red-black variant; for now the benchmark below shows that even the unbalanced tree is fast enough for the workloads people actually throw at one.

Try it

The playground below is a JavaScript port of the same API. Click a number to insert it. The SVG tree re-lays out on every change. The output panel below the tree prints every operation.

How it works

Insertion walks the tree from the root, comparing the new key to each node's key. Smaller goes left, larger goes right, equal replaces the payload. A node with no children gets the new value. The tree grows in O(h) where h is the current height; for a balanced tree that's O(log n).

Removal is the interesting case. When the node to remove has two children, we splice the in-order successor (the smallest value in the right subtree) into its place. The successor has at most one child, so the splice is a single pointer move.

The library is generic because it never touches the keys. It only asks the comparator are these two keys equal, or which is smaller? The caller decides what keys are. They can be integers, structs, strings, or anything else with a total order.

Benchmarks

Apple M-series, single thread, -O2:

These are not cryptographic. They are realistic for a workload that inserts, looks up, and removes the same data repeatedly — which is most of what application code does with a tree.

Tests

74 assertions across 8 test cases, all passing. The suite covers the empty tree, single insertion, multiple insertions, removal of leaf / one-child / two-child nodes, in-order walk, comparator edge cases, and a randomized fuzz test that runs 10k random operations and reconciles against a reference Python implementation.

The test framework is in the repo, no external dependency. Each test is a plain C function that calls ASSERT_* macros; the runner reports a pass/fail count and exits non-zero on any failure.

Source

The repository lives at github.com/404Piyush/bst-library. The public header, the implementation, and the test suite are the three files worth reading. The header is the contract. The implementation is about 250 lines. The test suite is about 200 lines and reads like a spec.

To build and test locally:

git clone https://github.com/404Piyush/bst-library
cd bst-library
make test

One of the gpu-engineering curriculum, a three-year systems and hardware roadmap. More projects incoming.