C Binary Search Trees

How it works

A binary search tree places smaller keys in one subtree and larger keys in the other according to a documented duplicate policy. Searching compares one node at a time and chooses one child. Its cost depends on height: a balanced tree can be logarithmic, while a chain-shaped tree can be linear. This fixture stores nodes as local objects so the search algorithm can be studied without mixing it with allocation and balancing. The tree borrows their addresses only while all of them remain alive.

Run it locally

Use a hosted C17 compiler in a separate lab folder. The command assumes a driver named cc; substitute gcc, clang or zig cc as appropriate. C does not currently run in Bhylu’s browser playground. Apache, PHP and MySQL are not needed for these C programs.

cc -std=c17 -Wall -Wextra -Wpedantic -Werror trees.c -o lesson

On Windows, use -o lesson.exe and run .\lesson.exe in PowerShell. On Unix-like systems run ./lesson. Math-library linking differs by toolchain; GCC on many Unix systems needs -lm after the source.

Download the complete C source. File-writing labs must run in an empty private directory, away from existing reports.

Example

#include <stdio.h>
#include <stdbool.h>

struct Node { int key; const struct Node *left; const struct Node *right; };
static bool contains(const struct Node *node, int key) {
    while (node != NULL) {
        if (key == node->key) { return true; }
        node = key < node->key ? node->left : node->right;
    }
    return false;
}

int main(void) {
    struct Node low = {12, NULL, NULL};
    struct Node high = {30, NULL, NULL};
    struct Node root = {20, &low, &high};
    printf("Found 30: %d\n", contains(&root, 30));
    printf("Found 25: %d\n", contains(&root, 25));
    return 0;
}

Expected result

Found 30: 1
Found 25: 0

The thirty search follows the right link and finds a match. Twenty-five also goes right, then left to a null child, proving absence under the ordering invariant. Insertion, deletion and balancing require additional invariants and tests. Do not infer ownership from the links: this fixture must not free its automatic nodes.