Binary search tree — insert, search and delete

#include <stdio.h>

stdio.h declares printf, puts, getchar and putchar. The input helper reads characters with getchar; the main program prints operation results using the output functions.

#include <stdlib.h>

stdlib.h declares strtol for converting an integer token. It also declares malloc and free, which the linked structures and tree programs use to obtain and release node storage.

#include <string.h>

string.h declares utilities such as memset. It is part of the shared header list; merely including a header does not call any function or change stored values.

#include <ctype.h>
#include <errno.h>

ctype.h supplies isspace for recognising whitespace. errno.h supplies errno so the program can detect a range error reported by strtol.

/* Read a complete integer token; reject bad or oversized input safely. */
int readInt(int *value) {

The comment states the purpose of readInt. Its int *value parameter receives the address of a caller variable. The helper returns 1 after storing a valid value there, or 0 on failure; these flags are separate from main’s process exit status.

    char token[64];
    int ch;
    size_t used = 0;

token holds up to 63 input characters and a null terminator. ch is int so it can distinguish character input from EOF. used starts at zero and counts the stored token characters.

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

getchar reads one character at a time. The loop discards whitespace before the token. The unsigned-char cast supplies an allowed argument to isspace. If EOF is reached before a token starts, return 0 without changing the caller variable.

    do {
        if (used < sizeof token - 1) token[used++] = (char)ch;

The do-while body handles the first non-whitespace character already read. The size check leaves one buffer slot for a null terminator. used++ uses the old index for storage, then advances the count.

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

When the buffer has no character space left, consume the rest of that token through whitespace or EOF, then return failure. The program does not silently treat a truncated prefix as the full input number.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));

Keep collecting until whitespace or EOF. The terminating whitespace has been consumed by getchar; it is not stored as part of the token.

    token[used] = '\0';
    char *end;
    errno = 0;

Write the null terminator after the stored token. end will identify where conversion stopped. Reset errno before strtol so a previous library error cannot be mistaken for this conversion’s result.

    long result = strtol(token, &end, 10);

strtol reads token in base 10 and returns a long. Passing &end lets it write the address of the first unconverted character. A sign such as - is allowed as part of a valid integer token.

    if (errno || *end != '\0' || result < -1000000 || result > 1000000) return 0;

A nonzero errno rejects a reported conversion error. *end must be the null terminator, so input such as 12x is rejected rather than accepted as 12. The allowed value range is -1,000,000 to 1,000,000.

    *value = (int)result;
    return 1;
}

After validation, cast result to int and assign it through *value. Return 1 for success. The brace ends readInt. The caller variable remains unchanged on the earlier failure returns.

#define MAX_NODES 100
typedef struct Node { int key; struct Node *left, *right; } Node;

At most 100 distinct keys are stored. Each Node holds key and left/right child pointers. The ordering policy puts smaller keys in the left subtree and larger keys in the right; duplicate insertions do not create nodes.

Node *insert(Node *root, int key, int count, int *status) {
    if (!root) {
        if (count == MAX_NODES) { *status = -2; return NULL; }

root is the current subtree root. count describes the current whole-tree node count. status is an output parameter: this branch sets -2 when a new node would exceed the limit and returns NULL for the still-empty subtree.

        Node *node = malloc(sizeof *node);
        if (!node) { *status = -1; return NULL; }
        node->key = key; node->left = node->right = NULL; *status = 1;
        return node;
    }

Allocate one Node. If allocation fails, set status to -1 and return NULL. Otherwise store key, initialise both children to NULL, set status to 1 and return the new node address. The caller must keep that returned address.

    if (key < root->key) root->left = insert(root->left, key, count, status);
    else if (key > root->key) root->right = insert(root->right, key, count, status);

For a smaller key, insert into the left subtree and assign the returned root to root->left. For a larger key use the right side. The assignment is essential when the chosen child was previously empty.

    else *status = 0;
    return root;
}

Equality sets status to 0 without allocating. Return the current root in every existing-node case so callers keep the surrounding tree connected. count changes later in main only after status 1.

int search(const Node *root, int key) {
    while (root) {
        if (key == root->key) return 1;
        root = key < root->key ? root->left : root->right;

While root is nonnull, return 1 on equality. Otherwise choose left for a smaller key or right for a larger key. The parameter is a local pointer copy, so moving it does not replace main’s root.

    }
    return 0;
}

The loop ends when no candidate node remains. Return 0 without dereferencing NULL. The brace closes search.

Node *deleteKey(Node *root, int key) {
    if (!root) return NULL;
    if (key < root->key) root->left = deleteKey(root->left, key);
    else if (key > root->key) root->right = deleteKey(root->right, key);

An empty subtree returns NULL. A smaller key recurses left and a larger key recurses right. Assign each returned subtree root back to its parent link because deletion may change that link.

    else {
        if (!root->left || !root->right) {
            Node *child = root->left ? root->left : root->right;
            free(root); return child;
        }

If either child is missing, select the other child, or NULL if both are missing. Free the current node and return the selected child. The caller reconnects that child in place of the removed root.

        Node *successor = root->right;
        while (successor->left) successor = successor->left;

Start in the right subtree, then move left until no left child remains. This finds the smallest key greater than the current key under the no-duplicates policy.

        root->key = successor->key;
        root->right = deleteKey(root->right, successor->key);
    }

Replacing the current key preserves its surrounding links. Then recursively remove the duplicate successor key from the right subtree and reconnect the returned root. Freeing the original two-child node directly would lose its child links.

    return root;
}

After any recursive repair, return root so the caller can reconnect it. Earlier zero/one-child branches already returned their replacement child.

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

Skip empty subtrees. Visit left, print the current key, then visit right. Because this tree enforces the BST rule, the output is ascending.

void freeTree(Node *root) {
    if (!root) return;
    freeTree(root->left); freeTree(root->right); free(root);
}

A null subtree needs no work. Free both subtrees recursively, then free the parent. No link from an already-freed parent is read afterward.

/* 1 key: insert; 2 key: search; 3 key: delete; 4: inorder; 0: exit. */
int main(void) {
    Node *root = NULL; int command, key, count = 0;

The command comment lists insert, search, delete, inorder and exit. root starts NULL and count starts at zero. The driver will keep count consistent with successful insertions and deletions.

    while (readInt(&command)) {
        if (command == 0) { freeTree(root); return 0; }
        if (command == 4) { printf("Inorder:"); inorder(root); putchar('\n'); continue; }

Command 0 frees the tree and returns success. Command 4 prints inorder without reading a key; continue jumps to the next command-reading iteration.

        if (!readInt(&key)) break;
        if (command == 1) {
            int status = 0; root = insert(root, key, count, &status);

The remaining operation branches need a key token. A missing key breaks to cleanup. For command 1, initialise status and assign insert’s returned root back to main’s root.

            if (status == 1) { ++count; puts("Inserted."); }
            else if (!status) puts("Duplicate ignored.");
            else puts("Insertion failed: node limit or allocation failure.");

Status 1 means a node was created, so increment count. Status 0 reports an ignored duplicate. Negative status reports allocation failure or the node limit without incrementing count.

        } else if (command == 2) puts(search(root, key) ? "Found." : "Not found.");

For command 2, the conditional expression uses search’s flag to choose Found or Not found. The root and count are unchanged.

        else if (command == 3) {
            if (search(root, key)) { root = deleteKey(root, key); --count; puts("Deleted."); }
            else puts("Key not found.");
        } else break;

For command 3, first search for the key. If found, retain deleteKey’s returned root, decrement count and print success. If absent, leave the tree and count unchanged. An unsupported command breaks out.

    }
    puts("Invalid or incomplete input. End with command 0.");
    freeTree(root); return 1;
}

After the loop, print the invalid/incomplete-input message, free the current tree and return failure. This is reached only when command 0 did not already finish successfully.