Tree traversals — non-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;
    const Node *stack[MAX_NODES]; int top = 0;
    stack[top++] = root;

Return for an empty tree. The stack stores pointers to existing nodes, not copies of subtrees. top is the number of stored pointers, initially zero. Push root using stack[top++] so it becomes the first pending node.

    while (top) {
        const Node *node = stack[--top]; printf(" %d", node->data);

Continue while top is nonzero. --top reduces the count before selecting the last pushed pointer, then print that node’s data. This is last-in, first-out behaviour.

        if (node->right) stack[top++] = node->right;
        if (node->left) stack[top++] = node->left;
    }
}

The right child is pushed first and the left child second. Because the stack pops the last pushed child first, this yields node-left-right order. The braces finish the loop and preorder. Only existing child pointers are pushed.

void inorder(const Node *root) {
    const Node *stack[MAX_NODES], *current = root; int top = 0;

current begins at root. The stack remembers ancestors whose left subtrees are being explored. top again counts stored pointers.

    while (current || top) {
        while (current) { stack[top++] = current; current = current->left; }

Continue while either current exists or a saved ancestor remains. Push current, then move left repeatedly. Reaching NULL means the next inorder visit must come from the saved ancestors.

        current = stack[--top]; printf(" %d", current->data);
        current = current->right;
    }
}

Pop the most recent ancestor, print its data and set current to its right child. The outer condition then repeats the left descent for that subtree. For an empty tree both current and top start empty, so no pop occurs.

void postorder(const Node *root) {
    if (!root) return;
    const Node *stack1[MAX_NODES], *stack2[MAX_NODES]; int top1 = 0, top2 = 0;
    stack1[top1++] = root;

For a nonempty tree, create two pointer stacks and zero their counts. Push root into stack1. stack2 will collect a temporary order that can be reversed by popping.

    while (top1) {
        const Node *node = stack1[--top1]; stack2[top2++] = node;

Pop a node from stack1 and push it into stack2. No data is printed at this stage, because postorder must put children before parents.

        if (node->left) stack1[top1++] = node->left;
        if (node->right) stack1[top1++] = node->right;
    }

The right child is processed before the left because it is pushed last. This collects node-right-left order in stack2; the final reversal will turn it into left-right-node order. The brace ends the collecting loop.

    while (top2) printf(" %d", stack2[--top2]->data);
}

Each --top2 removes the last stored pointer and prints its data. Popping reverses the collected order, giving the required left-right-node traversal. The next brace closes postorder.

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

Declare main’s root pointer and total count before calling the shared tree reader.

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

If readTree fails, print the message, release the reachable partial tree and return failure. Traversals run only after the complete input succeeds.

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

Each line prints a label, calls its traversal and adds a newline. The traversals use explicit stacks and leave the tree itself unchanged.

    freeTree(root); return 0;
}

Release the allocated nodes and return success. The traversal functions are non-recursive, but this program still uses recursive readTree and freeTree helpers for construction and cleanup.