Binary search tree diagram in C
2 min read
algorithms

Implementing a Binary Search Tree in C

Binary search trees are one of the most fundamental data structures in computer science. They offer O(log n) average-case performance for insertions, deletions, and lookups, making them a go-to choice for many applications.

Structure

A BST node typically looks like this:

typedef struct node {
    int key;
    struct node *left;
    struct node *right;
} node_t;

Core Operations

Insertion

Insertion follows a simple recursive pattern: compare the key with the current node, then recurse left or right until an empty spot is found.

node_t* insert(node_t *root, int key) {
    if (!root) {
        node_t *n = malloc(sizeof(node_t));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    return root;
}

Traversal

In-order traversal visits nodes in sorted order:

void inorder(node_t *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

Balancing

The main weakness of a basic BST is that it can degenerate into a linked list if keys are inserted in sorted order. Self-balancing variants like AVL trees or red-black trees solve this by enforcing invariants that keep the tree height logarithmic.

For memory-constrained embedded systems, an AVL tree is often preferable — the balancing logic is simpler than red-black, and the constant factor is lower.

Key Takeaways

  • BSTs provide fast lookups when balanced
  • Recursive implementations are elegant but watch your stack depth on embedded targets
  • Consider an iterative implementation if recursion depth is a concern
  • Always pair malloc with free — memory leaks in long-running embedded systems are catastrophic