Trees

In-Order Traversal (BST)

Recurse left, visit(node), recurse right. On a binary search tree, this emits values in ascending order — a useful invariant to teach.

Algorithm

Canonical tree 4(2(1, 3), 6(5, 7)) is a balanced BST. In-order traversal yields [1, 2, 3, 4, 5, 6, 7].

Basic Implementation

basic.c 
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

static TreeNode *make_tree(int v, TreeNode *l, TreeNode *r) {
    TreeNode *n = malloc(sizeof(TreeNode));
    n->value = v;
    n->left = l;
    n->right = r;
    return n;
}

static void free_tree(TreeNode *n) {
    if (n == NULL) return;
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

static void inorder(TreeNode *node, int *out, int *out_n) {
    if (node == NULL) {
        return;
    }
    inorder(node->left, out, out_n);
    out[(*out_n)++] = node->value;
    inorder(node->right, out, out_n);
}

int main(void) {
    TreeNode *n1 = make_tree(1, NULL, NULL);
    TreeNode *n3 = make_tree(3, NULL, NULL);
    TreeNode *n2 = make_tree(2, n1, n3);
    TreeNode *n5 = make_tree(5, NULL, NULL);
    TreeNode *n7 = make_tree(7, NULL, NULL);
    TreeNode *n6 = make_tree(6, n5, n7);
    TreeNode *root = make_tree(4, n2, n6);

    int output[16];
    int out_n = 0;
    inorder(root, output, &out_n);
    printf("[");
    for (int i = 0; i < out_n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", output[i]);
    }
    printf("]\n");
    free_tree(root);
    return 0;
}

Complexity

  • Time: O(n)
  • Space: O(h) call stack

Implementation notes

  • C: a small typedef struct TreeNode holds int value, struct TreeNode *left, and struct TreeNode *right. The recursion is the smallest possible reusable shape; NULL is the explicit empty-subtree sentinel.
  • The output buffer is a plain int output[16] plus an int out_n pass-by-pointer so the lesson does not lean on container abstractions the standard library does not provide.
  • The replay shows the running output array and the visited node value on each visit frame, with node(<value>) labels instead of raw pointer addresses.
in-order recursion `inorder(node->left, out, out_n); out[(*out_n)++] = node->value; inorder(node->right, out, out_n);`
BST invariant The same recursion on a binary search tree always emits values in ascending order.