Binary trees

Introduction

A binary tree is made of nodes that each have up to two children, left and right. The top node is the root; nodes with no children are leaves. Trees hold things that branch: folders, family trees, the moves of a game, and expressions such as (1 + 2) * 3.

The examples use this tree:

        1
      /   \
     2     3
    / \
   4   5

Lists are good for things in a line, but much of the world branches: a folder holds folders, and a decision leads to more decisions. A tree stores that shape directly, and recursion is the natural way to walk through it.

How it works

Counting and measuring

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

typedef struct tree {
    int value;
    struct tree *left, *right;
} Tree;

Tree *node(int value, Tree *left, Tree *right) {
    Tree *t = malloc(sizeof(Tree));
    t->value = value;
    t->left = left;
    t->right = right;
    return t;
}

int count(Tree *t) {
    if (t == NULL) return 0;
    return 1 + count(t->left) + count(t->right);
}

int height(Tree *t) {
    if (t == NULL) return 0;
    int l = height(t->left);
    int r = height(t->right);
    return 1 + (l > r ? l : r);
}

void free_tree(Tree *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

int main(void) {
    Tree *root = node(1, node(2, node(4, NULL, NULL), node(5, NULL, NULL)), node(3, NULL, NULL));
    printf("nodes: %d\n", count(root));
    printf("height: %d\n", height(root));
    free_tree(root);
    return 0;
}

Most questions about a tree have the same recursive shape: answer for the left subtree, answer for the right subtree, combine.

• count = 1 + count(left) + count(right)
• height = 1 + the larger height of the two subtrees. Here an empty tree has height 0, so it counts levels. Some books count edges instead, which gives one less.

free_tree must free the children before the node, so it is a postorder traversal. Freeing the node first would lose the pointers to its children.

Syntax

typedef struct tree {
    int value;
    struct tree *left, *right;
} Tree;

void visit(Tree *t) {
    if (t == NULL) return;   // an empty tree: nothing to do
    visit(t->left);
    visit(t->right);
}

Example

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

typedef struct tree {
    int value;
    struct tree *left, *right;
} Tree;

Tree *node(int value, Tree *left, Tree *right) {
    Tree *t = malloc(sizeof(Tree));
    t->value = value;
    t->left = left;
    t->right = right;
    return t;
}

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

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

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

int main(void) {
    Tree *root = node(1, node(2, node(4, NULL, NULL), node(5, NULL, NULL)), node(3, NULL, NULL));
    preorder(root);
    printf("\n");
    inorder(root);
    printf("\n");
    postorder(root);
    printf("\n");
    return 0;
}

Every traversal is a small recursive function: do nothing for an empty tree (NULL), otherwise handle the node and both subtrees. They differ only in when the node itself is printed:

Watch the call stack grow down the left side of the tree, return at each NULL, and then go right.

Line by line

1. node allocates a tree node and fills in its value and two children.
2. preorder prints the node first and then visits its left and right subtrees.
3. inorder visits the left subtree, prints the node, then visits the right.
4. postorder visits both subtrees and prints the node last.
5. The nested calls in main build the five-node tree, innermost nodes first.
6. Each traversal starts from the root and prints one line.

Expected result

1 2 4 5 3 
4 2 5 1 3 
4 5 2 3 1 

In the real world

Web browsers hold each page as a tree of elements, and compilers turn programs into syntax trees before translating them. File managers walk a tree of folders whenever they work out how much space one takes up.

Common mistakes

• Forgetting the NULL base case: the recursion follows a NULL pointer and crashes.
• Freeing a node before its children, which leaks the subtrees.
• Mixing up the traversal orders: in inorder, the node is printed in between its subtrees.

Best practices

• Write the NULL case first in every recursive function.
• Trace a small tree by hand before trusting a new traversal.
• Say whether your height counts levels or edges, because books differ.

Summary

A binary tree is made of nodes with up to two children. The three depth-first traversals differ only in when the node is handled, and most tree questions combine the answers for the two subtrees.

Mark lesson complete