C Binary Trees

A binary tree is a data structure made of nodes, where each node holds a value and points to at most two children, called the left child and the right child. Binary trees let you represent hierarchical relationships and, in the common case of a binary search tree (BST), they let you store data so that searching, inserting, and deleting can all be done in roughly logarithmic time instead of scanning a whole array. Because C has no built-in tree type, you build binary trees yourself out of structs and pointers — which is also the best way to truly understand how they work.

Overview: How Binary Trees Work

A binary tree is built from nodes. Each node is a small struct containing a data value and two pointers: one to a left subtree and one to a right subtree. A pointer that is NULL means “no child there.” The topmost node is called the root; a node with no children is called a leaf. Every node (other than the root) has exactly one parent, and the tree as a whole is really just a chain of dynamically allocated nodes linked together, similar in spirit to a linked list but branching in two directions instead of one.

Because nodes are allocated on the heap with malloc, the tree lives in scattered memory locations, and the only way to reach a node is by following pointers starting from the root. This means the shape of the tree, and how fast operations are, depends entirely on the order in which you insert data.

A plain binary tree places nodes anywhere the programmer chooses. A far more useful variant is the binary search tree, which enforces an ordering rule: for every node, every value in its left subtree is smaller than the node’s value, and every value in its right subtree is larger. This rule is what makes searching fast — at each node you can discard an entire half of the remaining tree, just like binary search on a sorted array. In a balanced BST with n nodes, search, insert, and delete all run in O(log n) time. However, if you insert already-sorted data, the tree degenerates into something that behaves like a linked list, and operations slow down to O(n). (Self-balancing trees like AVL trees and red-black trees solve this problem, but they build on the same node structure shown here.)

Traversing a tree means visiting every node exactly once in some defined order. The three classic recursive orders are:

• Inorder (left, node, right) — visits nodes of a BST in ascending sorted order.
• Preorder (node, left, right) — visits the root first; useful for copying or serializing a tree.
• Postorder (left, right, node) — visits children before the parent; useful for deleting a tree safely, because you free children before their parent.

Syntax

A binary tree node is typically declared like this:

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

Part	Meaning
int data	The value stored in this node (can be any type: int, float, a struct, etc.)
struct Node *left	Pointer to the left child, or NULL if there isn’t one
struct Node *right	Pointer to the right child, or NULL if there isn’t one

Nodes are created dynamically with malloc, since the number of nodes is not known ahead of time:

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

Recursive functions are the natural way to operate on trees, because a subtree is itself a smaller binary tree — the same logic that applies to the whole tree applies to each subtree.

Examples

Example 1: Building a Tree Manually and Traversing It

This example builds a small tree by hand (without any insertion rule) and prints it using an inorder traversal.

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

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void inorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main(void) {
    struct Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->left->left = createNode(3);
    root->left->right = createNode(7);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

Output:

Inorder traversal: 3 5 7 10 15 

Here the tree’s shape was chosen by hand, not by an insertion rule, yet the values still happen to satisfy the BST ordering property, so the inorder traversal prints them in ascending order. Note that each node must be freed individually with free — a manually built tree has no automatic cleanup function.

Example 2: A Real Binary Search Tree with Insert, Search, and All Three Traversals

This is the realistic way to use a binary tree: insert values one at a time following the BST rule, then search and traverse it.

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

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

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

struct Node* insert(struct Node* 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;
}

struct Node* search(struct Node* root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }
    if (value < root->data) {
        return search(root->left, value);
    }
    return search(root->right, value);
}

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

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

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

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

int main(void) {
    struct Node* 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("Inorder:   ");
    inorder(root);
    printf("\n");

    printf("Preorder:  ");
    preorder(root);
    printf("\n");

    printf("Postorder: ");
    postorder(root);
    printf("\n");

    int target = 40;
    struct Node* found = search(root, target);
    if (found != NULL) {
        printf("Found %d in the tree\n", target);
    } else {
        printf("%d not found\n", target);
    }

    freeTree(root);
    return 0;
}

Output:

Inorder:   20 30 40 50 60 70 80 
Preorder:  50 30 20 40 70 60 80 
Postorder: 20 40 30 60 80 70 50 
Found 40 in the tree

Inserting 50, 30, 70, 20, 40, 60, 80 in that order produces a balanced tree with 50 at the root, 30 and 70 as its children, and 20/40 and 60/80 as their respective children. The inorder traversal prints the values in sorted order — proof the BST property holds. Preorder shows the root first, then dives left before right. Postorder visits both children before their parent, which is exactly the safe order for freeing memory.

Example 3: Deleting a Node and Measuring Tree Height

Deletion is the trickiest BST operation because the node being removed might have zero, one, or two children. This example also computes the tree’s height and node count.

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

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

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

struct Node* insert(struct Node* 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;
}

struct Node* findMin(struct Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

struct Node* deleteNode(struct Node* root, int value) {
    if (root == NULL) {
        return NULL;
    }
    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        struct Node* successor = findMin(root->right);
        root->data = successor->data;
        root->right = deleteNode(root->right, successor->data);
    }
    return root;
}

int height(struct Node* root) {
    if (root == NULL) {
        return -1;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int countNodes(struct Node* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

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

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

int main(void) {
    struct Node* 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("Before deletion: ");
    inorder(root);
    printf("\n");
    printf("Height: %d, Nodes: %d\n", height(root), countNodes(root));

    root = deleteNode(root, 30);

    printf("After deleting 30: ");
    inorder(root);
    printf("\n");
    printf("Height: %d, Nodes: %d\n", height(root), countNodes(root));

    freeTree(root);
    return 0;
}

Output:

Before deletion: 20 30 40 50 60 70 80 
Height: 2, Nodes: 7
After deleting 30: 20 40 50 60 70 80 
Height: 2, Nodes: 6

Node 30 has two children (20 and 40), so deleteNode finds its inorder successor — the smallest value in its right subtree, which is 40 — copies that value into 30’s position, and then deletes the original 40 node (which has no children, so that removal is trivial). This keeps the BST property intact without having to physically move more than one node’s data.

How It Works Step by Step (Under the Hood)

• Insertion: Starting at the root, compare the new value to the current node. Go left if smaller, right if larger, and repeat until you fall off the tree (hit NULL) — that’s where the new node is attached.
• Search: Identical logic to insertion, but you stop and return the node as soon as you find a match, or return NULL if you fall off the tree.
• Deletion: Locate the node. If it has zero or one child, splice it out and reconnect its parent directly to its (possibly absent) child. If it has two children, replace its value with its inorder successor (or predecessor) and delete that successor node instead, which is guaranteed to have at most one child.
• Traversal: Each traversal function calls itself on the left subtree and right subtree, visiting the current node’s value either before, between, or after those two recursive calls. The call stack itself acts as the “memory” of where to return to, which is why these are naturally recursive rather than needing an explicit stack (though an explicit stack can be used for iterative versions).
• Memory: Every node is a separate heap allocation. There is no single contiguous block, so the tree cannot be indexed by arithmetic like an array — traversal always means following pointers.

Common Mistakes

Mistake 1: Forgetting to Capture the Return Value of Insert/Delete

Both insert and deleteNode return a (possibly new) subtree root. If you ignore the return value, the tree doesn’t actually change.

/* Wrong: the insertion is silently lost */
insert(root, 25);

/* Correct: reassign root (or the appropriate child pointer) */
root = insert(root, 25);

This matters especially for the very first insertion, when root is NULL and insert must allocate the first node and hand its pointer back to the caller.

Mistake 2: Leaking Memory by Not Freeing the Tree

Every node created with malloc must eventually be freed. Freeing only the root leaks every other node in the tree.

/* Wrong: leaks every node except root */
free(root);

/* Correct: free children first, then the node itself */
void freeTree(struct Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

Freeing in postorder is essential: if you freed the parent before its children, you would lose the pointers needed to reach and free those children, causing a memory leak.

Mistake 3: Assuming the Tree Stays Balanced

Inserting already-sorted data into a plain BST (e.g. 1, 2, 3, 4, 5 in order) produces a tree that is really just a right-leaning linked list, degrading every operation to O(n). Randomizing insertion order, or using a self-balancing structure (AVL tree, red-black tree) when input order can’t be controlled, avoids this trap.

Best Practices

• Always check malloc‘s return value in production code — it can return NULL if memory allocation fails.
• Always reassign the result of insert/deleteNode back to the pointer you passed in (root = insert(root, value);).
• Write and use a recursive freeTree function whenever a tree goes out of scope to avoid memory leaks.
• Use inorder traversal to verify a BST’s ordering invariant while debugging — the output must be sorted.
• Prefer iterative traversal with an explicit stack for extremely deep trees, since deep recursion can overflow the call stack.
• Keep node comparison logic (like value < root->data) consistent everywhere — insert, search, and delete must all agree on ordering, or the tree becomes corrupted.
• Consider a self-balancing tree (AVL, red-black) if your application inserts data in a mostly sorted order, since a plain BST offers no guarantee against degenerating into a linked list.

Practice Exercises

• Exercise 1: Write a function int findMax(struct Node* root) that returns the largest value in a BST without using recursion (hint: keep following the right child until it’s NULL).
• Exercise 2: Write a function int isBST(struct Node* root, int min, int max) that checks whether a given binary tree actually satisfies the BST ordering property, returning 1 if valid and 0 otherwise.
• Exercise 3: Modify Example 2 to build a tree from the values {15, 10, 20, 8, 12, 17, 25} and print its level-order traversal (breadth-first, visiting each depth left to right) using a simple array-based queue. Expected inorder output for a sanity check: 8 10 12 15 17 20 25.

Summary

• A binary tree node holds a value plus pointers to at most two children, left and right, allocated dynamically with malloc.
• A binary search tree keeps values ordered — everything smaller than a node goes left, everything larger goes right — which makes search, insert, and delete O(log n) on average.
• Inorder, preorder, and postorder are the three standard recursive traversal orders, each useful for different purposes (sorted output, copying, and safe deletion respectively).
• Deletion is the most complex operation because a node with two children must be replaced by its inorder successor (or predecessor) rather than removed directly.
• Always reassign the result of insert/delete calls back to the correct pointer, and always free every node (postorder) to avoid memory leaks.
• An unbalanced BST built from sorted input degrades to O(n) performance; self-balancing trees solve this but build on the same fundamentals shown here.