Tree traversals — recursive

#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 data; struct Node *left, *right; } Node;

MAX_NODES is 100. Each Node stores data and the addresses of its left and right children. A null child pointer represents an empty subtree.

/* Preorder input: value, left subtree, right subtree; -1 means NULL. */
int readTree(Node **root, int *count) {

The comment describes value, left subtree, right subtree order, using -1 as an empty-subtree marker. Node **root receives the address of a caller-owned child or root pointer, allowing this helper to assign that pointer.

    int value;
    *root = NULL;
    if (!readInt(&value)) return 0;
    if (value == -1) return 1;

Begin with *root = NULL so failed or empty input leaves a known pointer state. Return failure if no valid integer is read. A value of -1 represents an empty subtree and returns success without allocating a node.

    if (*count == MAX_NODES) return 0;
    Node *node = malloc(sizeof *node);
    if (!node) return 0;

Reject another nonempty node when count already equals 100. Allocate one Node and return failure on a null allocation result. The counter is shared across all recursive calls.

    node->data = value; node->left = node->right = NULL;
    *root = node; ++(*count);

Set data, initialise both children to NULL, then store node through the output pointer and increment the total count. If a later child read fails, the partial tree remains reachable for cleanup.

    return readTree(&node->left, count) && readTree(&node->right, count);
}

&node->left and &node->right are addresses of the actual child pointers. Both reads must succeed for the function to return success. Logical AND skips reading the right subtree when the left read fails.

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

Return immediately on a null pointer. Recursively release the left subtree and then the right, then free the current node. Releasing the parent last avoids needing to read its links after free.

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

Stop on NULL. For a real node, print its data, recursively traverse left, then right. For root 1 with children 2 and 3, this yields 1, 2, 3. Returning from a recursive call resumes at the next statement in its caller.

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

The null-pointer check is the base case. Traverse left, print the current node, then traverse right. For the same three-node tree, the order is 2, 1, 3. Inorder is sorted only when the input tree also satisfies the BST ordering rule.

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

Again stop on NULL. Traverse left, then right, and print the current node last. The three-node example gives 2, 3, 1. A parent is printed only after both recursive calls return.

int main(void) {
    Node *root = NULL; int count = 0;

main declares the root pointer and shared count. readTree will update them through their addresses.

    if (!readTree(&root, &count)) {
        puts("Invalid tree input or allocation failure."); freeTree(root); return 1;
    }

A failed read may already have allocated some nodes. Print the error, pass the reachable root to freeTree, and return failure instead of traversing an incomplete input as though it were valid.

    printf("Preorder:"); preorder(root); putchar('\n');
    printf("Inorder:"); inorder(root); putchar('\n');
    printf("Postorder:"); postorder(root); putchar('\n');

Print a label, call the appropriate traversal on the same root, then print a newline. These traversals do not modify links, so all three see the same tree.

    freeTree(root); return 0;
}

freeTree releases every allocated node. Return success from main only after the traversal output and cleanup are complete.