Binary Search Tree (BST) in C Programming

A Binary Search Tree (BST) organizes hierarchical data for O(log N) average-case search, insertion, and deletion. Master recursive tree node structures, In-Order traversals, and heap management in C.

A Binary Search Tree (BST) is a hierarchical node-based data structure where each node holds a key, a left child pointer, and a right child pointer. The BST invariant dictates that all keys in the left subtree must be strictly less than the node's key, and all keys in the right subtree must be strictly greater.

When balanced, search, insertion, and deletion operations execute in O(log N) logarithmic time. An In-Order traversal (Left -> Root -> Right) visits nodes in strictly ascending sorted order.

In C, trees are implemented using dynamically allocated struct pointers. Deleting a node with two children requires replacing it with its in-order successor (the smallest key in its right subtree) before freeing the original node.

This example covers insertion and traversal: insert returns 1 on success and 0 if allocation fails, leaving existing nodes intact. Duplicate keys are ignored to preserve the strict BST invariant. The caller frees the partially built tree before reporting an allocation error.

Interactive Runnable C Implementation

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

typedef struct BSTNode {
    int val;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

/* Return 0 on allocation failure without changing existing nodes. */
int insert(BSTNode **root, int val) {
    if (*root == NULL) {
        BSTNode *node = malloc(sizeof *node);
        if (node == NULL) return 0;
        node->val = val;
        node->left = node->right = NULL;
        *root = node;
        return 1;
    }
    if (val < (*root)->val) return insert(&(*root)->left, val);
    if (val > (*root)->val) return insert(&(*root)->right, val);
    return 1; /* Ignore duplicate keys. */
}

void inorder(const BSTNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

void freeBST(BSTNode *root) {
    if (root != NULL) {
        freeBST(root->left);
        freeBST(root->right);
        free(root);
    }
}

int main(void) {
    BSTNode *root = NULL;
    const int keys[] = {50, 30, 20, 40, 70, 60, 80};
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; i++) {
        if (!insert(&root, keys[i])) {
            fputs("Unable to allocate a BST node.\n", stderr);
            freeBST(root);
            return EXIT_FAILURE;
        }
    }

    printf("BST In-Order Sorted Traversal: ");
    inorder(root);
    printf("\n");

    freeBST(root);
    return EXIT_SUCCESS;
}

Open example in compiler

Expected Output

BST In-Order Sorted Traversal: 20 30 40 50 60 70 80