Binary Trees

A tree represents hierarchical data: one root, branches to children, and leaves at the bottom. File systems, HTML documents, expression trees, decision trees, and organizational charts all use this shape.

A binary tree is a tree where each node has at most two children, usually called left and right. A binary tree does not automatically impose ordering; it only imposes shape. Ordering rules belong to binary search trees, covered in the next chapter.

Binary trees are useful because many recursive problems naturally split into two subproblems: left and right, yes and no, smaller and larger, true branch and false branch. The structure is also the foundation for heaps, expression trees, decision trees, search trees, Huffman coding trees, and parsing algorithms.

Terminology

• Root: the top node of the tree
• Parent: a node directly above another node
• Child: a node directly below another node
• Leaf: a node with no children
• Depth: number of edges from the root to a node
• Height: maximum depth of any leaf in the tree
• Subtree: a node together with all its descendants

Tree Types

These terms are not interchangeable. A heap requires a complete binary tree. A binary search tree requires an ordering invariant. A balanced tree requires a height constraint. A general binary tree requires none of these beyond “at most two children.”

Properties

For a binary tree with n nodes:

• number of edges is n - 1 if the tree is non-empty
• maximum number of nodes at depth d is 2^d
• maximum number of nodes in a tree of height h is 2^(h + 1) - 1
• minimum possible height is floor(log2 n) for a packed tree
• maximum possible height is n - 1 for a skewed tree

Height matters because most root-to-leaf operations cost O(h).

Node Layout

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

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

TreeNode *tree_node_new(int value) {
    TreeNode *node = malloc(sizeof(TreeNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

This representation is recursive: every child pointer either points to another TreeNode or to NULL.

Recursive Shape

Many tree algorithms have the same structure:

void visit(TreeNode *node) {
    if (node == NULL) return;
    visit(node->left);
    visit(node->right);
}

The base case is the empty subtree. The recursive case handles the current node plus its left and right subtrees. Once this pattern is comfortable, traversal, counting, height calculation, copying, and freeing become variations on the same idea.

Insertion

For a plain binary tree, there is no key-ordering rule. One common insertion policy is level-order insertion: fill the tree from left to right, top to bottom, like a complete binary tree.

#define MAX_Q 256

TreeNode *binary_tree_insert(TreeNode *root, int value) {
    TreeNode *node = tree_node_new(value);
    if (root == NULL) return node;

    TreeNode *queue[MAX_Q];
    int front = 0, back = 0;
    queue[back++] = root;

    while (front < back) {
        TreeNode *cur = queue[front++];
        if (cur->left == NULL) {
            cur->left = node;
            return root;
        }
        queue[back++] = cur->left;

        if (cur->right == NULL) {
            cur->right = node;
            return root;
        }
        queue[back++] = cur->right;
    }
    return root;
}

This insertion is O(n) because it may scan many nodes to find the first open child position.

Counting

int tree_count(const TreeNode *node) {
    if (node == NULL) return 0;
    return 1 + tree_count(node->left) + tree_count(node->right);
}

int tree_count_leaves(const TreeNode *node) {
    if (node == NULL) return 0;
    if (node->left == NULL && node->right == NULL) return 1;
    return tree_count_leaves(node->left) + tree_count_leaves(node->right);
}

int tree_height(const TreeNode *node) {
    if (node == NULL) return -1;
    int left_h = tree_height(node->left);
    int right_h = tree_height(node->right);
    return 1 + (left_h > right_h ? left_h : right_h);
}

Each function visits every node once, so each is O(n).

DFS Traversals

A traversal visits every node exactly once. The three recursive depth-first traversals differ only in when the current node is processed.

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

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

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

Level Order

Level-order traversal visits nodes by depth using a queue.

void level_order(TreeNode *root) {
    if (root == NULL) return;

    TreeNode *queue[MAX_Q];
    int front = 0, back = 0;
    queue[back++] = root;

    while (front < back) {
        TreeNode *cur = queue[front++];
        printf("%d ", cur->value);
        if (cur->left) queue[back++] = cur->left;
        if (cur->right) queue[back++] = cur->right;
    }
}

All traversals above are O(n) time because every node is visited once. Recursive traversals use O(h) call-stack space, where h is tree height. Level-order traversal uses O(w) queue space, where w is the maximum width of the tree.

Expression Trees

An expression tree stores operands in leaves and operators in internal nodes:

      *
     / \
    +   5
   / \
  2   3

This represents (2 + 3) * 5. Traversal gives different notations:

• preorder: * + 2 3 5 (prefix)
• inorder: 2 + 3 * 5 (infix, usually needs parentheses)
• postorder: 2 3 + 5 * (postfix)

Tree traversal changes how structured expressions are represented; it is not just a printing exercise.

Array Layout

Complete binary trees can be stored in arrays without pointers:

left child  = 2*i + 1
right child = 2*i + 2
parent      = (i - 1) / 2

This representation is used by heaps. It is not suitable for sparse arbitrary trees because empty child positions would waste many array slots.

Freeing a Tree

Postorder is the safe order for freeing nodes because children are freed before the parent pointer disappears.

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

Pitfalls

• Assuming every binary tree is a binary search tree
• Confusing height and number of nodes
• Forgetting the base case for NULL
• Using inorder traversal and expecting sorted output from a non-BST
• Freeing a parent before its children
• Ignoring recursion depth on highly skewed trees

Exercises

1. Insert {5, 3, 7, 1, 4, 6, 8} using level-order insertion and draw the resulting tree.
2. Write the preorder, inorder, postorder, and level-order traversal outputs.
3. Explain why inorder traversal is not automatically sorted for a general binary tree.
4. Implement tree_free and explain why preorder freeing would be unsafe.