Binary Trees

A binary search tree keeps every node's left subtree smaller and right subtree larger, making lookup, insertion, and in-order traversal all naturally recursive:

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

TreeNode *insert(TreeNode *root, int value) {
    if (root == NULL) {
        TreeNode *node = malloc(sizeof(TreeNode));
        node->value = value;
        node->left = node->right = NULL;
        return node;
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

void printInOrder(TreeNode *root) {
    if (root == NULL) return;
    printInOrder(root->left);
    printf("%d ", root->value);
    printInOrder(root->right);
}

An in-order traversal of a binary search tree always visits values in sorted order — a direct consequence of the left-smaller, right-larger rule applied at every node.