Binary trie — eight-bit integer keys

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define BITS 8
#define MAX_VALUES 100
#define MAX_NODES (1 + MAX_VALUES * BITS)
typedef struct Node { struct Node *child[2]; int terminal; } Node;
Node pool[MAX_NODES]; int used = 1, count = 0;
Node *root = &pool[0];

Each node has child[0], child[1] and a terminal flag. A zero-initialised static pool provides root plus enough nodes for the capped number of eight-bit values. root is pool[0], used begins at 1, and count starts at zero.

int search(int value) {
    Node *p = root;
    for (int bit = BITS - 1; bit >= 0; --bit) {
        int direction = (value >> bit) & 1;

Start at root and visit bit positions 7 down to 0. (value >> bit) & 1 selects child 0 or 1, preserving leading zero bits in the fixed-width representation.

        if (!p->child[direction]) return 0;
        p = p->child[direction];
    }
    return p->terminal;
}

If a selected child does not exist, the value is absent. Otherwise follow it. After all eight links, return terminal so the complete stored value, not just a partial path, determines success.

void insert(int value) {
    Node *p = root;
    for (int bit = BITS - 1; bit >= 0; --bit) {
        int direction = (value >> bit) & 1;
        if (!p->child[direction]) p->child[direction] = &pool[used++];
        p = p->child[direction];

Again scan the eight bits. If a required child is absent, take the next unused zero-initialised pool node. Existing prefixes are reused rather than duplicated.

    }
    p->terminal = 1; ++count;
}

After the path loop, set terminal and increment count. The driver checks duplicates and capacity before calling this helper, so it counts only a new distinct value.

void display(const Node *p, int depth, int value) {
    if (!p) return;
    if (depth == BITS) { if (p->terminal) printf(" %d",value); return; }
    display(p->child[0],depth + 1,value * 2);
    display(p->child[1],depth + 1,value * 2 + 1);
}

At depth eight, print only terminal values. Otherwise append a zero bit using value * 2 or a one bit using value * 2 + 1. Zero-first traversal produces ascending numeric order.

/* 1 value: insert, 2 value: exact search, 3: sorted values, 0: exit.
   Values 0..255 use an explicit eight-bit width. At most 100 distinct values. */
int main(void) {
    int command, value;
    while (readInt(&command)) {
        if (!command) return 0;
        if (command == 3) { printf("Values:"); display(root,0,0); putchar('\n'); continue; }

The interface accepts only 0–255 values and at most 100 distinct entries. Exit returns success. Display starts at depth zero and value zero, then continues to the next command.

        if ((command != 1 && command != 2) || !readInt(&value) || value < 0 || value > 255) return invalid();
        if (command == 2) puts(search(value) ? "Found." : "Not found.");
        else if (search(value)) puts("Duplicate ignored.");
        else if (count == MAX_VALUES) puts("Trie is full.");
        else { insert(value); puts("Inserted."); }

Reject unsupported commands or values outside the eight-bit range. Searches do not change the trie. Insertions ignore an existing terminal value and reject the capacity limit before creating a path.

    }
    return invalid();
}

If input ends without command 0, report incomplete input. The static pool needs no per-node free operation.