Binary Trees

A binary tree is a hierarchical data structure in which each node has at most two children, conventionally called left and right. Trees model naturally hierarchical data — file systems, organization charts, parsed expressions — and, in the special case of a binary search tree (BST), they let you search, insert, and delete in roughly logarithmic time.

The Node Structure

Each node stores a piece of data and two pointers to its children. A NULL child pointer means "no subtree here."

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

Binary Search Tree Ordering Rule

A BST keeps its nodes in a specific order: for every node, every value in its left subtree is smaller, and every value in its right subtree is larger. This invariant is what makes searching fast — at each node you can discard an entire half of the remaining tree.

Insertion (Recursive)

Inserting into a BST is naturally recursive: compare the new value against the current node, then recurse into the left or right subtree depending on the comparison, until you find an empty spot (`NULL`) to attach the new node. See the Recursion page for background on how recursive functions like this one unwind.

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

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

TreeNode *createNode(int value) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (node != NULL) {
        node->data = value;
        node->left = NULL;
        node->right = NULL;
    }
    return node;
}

TreeNode *insert(TreeNode *root, int value) {
    if (root == NULL) {
        return createNode(value); /* found the empty spot */
    }

    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    /* Equal values are ignored here to keep the tree free of duplicates. */

    return root;
}

In-Order Traversal: Printing Sorted Order

Visiting a BST in-order (left subtree, then the node itself, then right subtree) always produces the values in ascending sorted order. This is one of the most useful properties of a BST — sorting falls out of the structure for free.

void inOrderTraversal(const TreeNode *root) {
    if (root == NULL) {
        return; /* base case: empty subtree */
    }
    inOrderTraversal(root->left);
    printf("%d ", root->data);
    inOrderTraversal(root->right);
}

Searching a BST

TreeNode *search(TreeNode *root, int value) {
    if (root == NULL || root->data == value) {
        return root; /* either found it, or hit a dead end */
    }
    if (value < root->data) {
        return search(root->left, value);
    }
    return search(root->right, value);
}

Freeing a Tree

Every node allocated with malloc must eventually be freed. The natural way to visit every node exactly once for cleanup is a post-order traversal: free the children before freeing the node itself.

void freeTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

Full Compilable Example

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

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

TreeNode *createNode(int value) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (node != NULL) {
        node->data = value;
        node->left = NULL;
        node->right = NULL;
    }
    return node;
}

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

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

void freeTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main(void) {
    TreeNode *root = NULL;
    int values[] = { 50, 30, 70, 20, 40, 60, 80 };
    int n = sizeof(values) / sizeof(values[0]);

    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }

    printf("In-order (sorted): ");
    inOrderTraversal(root);
    printf("\n");

    freeTree(root);
    return 0;
}

Note

This program prints `20 30 40 50 60 70 80` — the same values inserted in an arbitrary order, but visited in ascending sorted order thanks to the BST invariant plus in-order traversal.

Traversal Orders at a Glance

Traversal	Visit order	Typical use
Pre-order	Node, Left, Right	Copying/serializing a tree
In-order	Left, Node, Right	Reading BST values in sorted order
Post-order	Left, Right, Node	Deleting/freeing a tree safely

Tip

Recursive tree functions are usually the clearest way to express tree logic in C — each call handles one node and trusts the recursive calls to correctly handle the subtrees.

Warning

A BST built by inserting already-sorted data degenerates into a linked list (every node has only a right child), losing the O(log n) benefit. Balanced tree variants like AVL or red-black trees solve this by rebalancing after insertions.