Binary trees and traversals

Lists, stacks and queues arrange items in a line. Many kinds of data are not linear but hierarchical: a file system, an organization chart, the structure of an arithmetic expression, the sections of a document, a decision process that asks one question and then another depending on the answer. The data structure for hierarchies is the tree. This lesson introduces trees in general and binary trees in particular, the vocabulary used to describe them, how they are stored in memory, and the four standard ways of visiting every node. Lesson 8 then specializes the binary tree into the binary search tree, and lesson 9 into the heap.

Jonah's tree this week is small but real. The NS-4 classifies each vehicle from its measured length, its speed and the number of axles detected by the loops. The classification rules were worked out by Northway's traffic engineers as a decision tree: first ask whether the length is under 6 m, then, on one branch, whether there are more than two axles, and so on, until a leaf names the class. The firmware stores that tree as data, so that a city with different classes can be given a new tree without new code, and evaluates it for every passing vehicle. On the server, a second kind of tree, an expression tree, represents the threshold conditions that technicians type into the maintenance port.

Tree vocabulary

A tree is a collection of nodes connected by edges, with one special node, the root, at the top, and with exactly one path from the root to every other node. Each node except the root has exactly one parent, the node directly above it; the nodes directly below a node are its children. Nodes with no children are leaves; the others are internal nodes. A node's descendants are its children, their children and so on; its ancestors are its parent, its parent's parent and so on up to the root. Any node together with all its descendants forms a subtree, which is itself a tree. This self-similarity is why recursion, from lesson 6, is the natural tool for trees.

Two measurements describe a tree's shape. The depth of a node is the number of edges on the path from the root to it, so the root has depth 0. The height of a tree is the largest depth of any node, the length of the longest path from the root to a leaf. Height matters because most tree operations walk a single path from the root downward, so their cost is proportional to the height. A tree whose nodes are spread evenly is short and bushy; a tree whose nodes form a single chain is tall and thin, and behaves like a linked list.

Binary trees

A binary tree is a tree in which each node has at most two children, called the left child and the right child. The distinction between left and right matters: a node with only a left child is a different tree from one with only a right child. Several special shapes have names. A full binary tree is one in which every node has either zero or two children. A perfect binary tree is full and has all its leaves at the same depth; a perfect tree of height h has 2ʰ⁺¹ − 1 nodes. A complete binary tree has every level full except possibly the last, which is filled from the left; this is the shape a heap uses. The relationship between height and the number of nodes is the central fact about binary trees.

Storing a binary tree

The usual representation is linked: each node is a small record holding the data and two pointers, left and right, which are null where a child is missing. The tree is reached through a pointer to its root. This representation handles any shape and lets subtrees be attached and detached by changing a pointer. It costs two pointers per node, and like a linked list it scatters nodes across memory. Some implementations add a parent pointer to each node, which makes it easy to walk upward but costs a third pointer.

A complete binary tree can instead be stored in an array with no pointers at all. Put the root at index 0, then the nodes of each level from left to right. The children of the node at index i are then at 2i + 1 and 2i + 2, and its parent is at ⌊(i − 1)/2⌋. Because the tree is complete there are no gaps in the array. This compact, cache-friendly layout is how heaps are stored, and it is also how the NS-4 firmware stores its classification tree: the tree is small and fixed, so it is laid out in flash as an array of nodes, each holding a test and the indexes of its two children, with no pointers that would need fixing up after loading.

Traversals

Visiting every node of a tree exactly once is called a traversal. Because a tree branches, there is more than one natural order. The three depth-first orders are defined recursively and differ only in when the node itself is visited relative to its two subtrees. In a preorder traversal you visit the node, then traverse its left subtree, then its right subtree. In an inorder traversal you traverse the left subtree, visit the node, then traverse the right subtree. In a postorder traversal you traverse both subtrees and visit the node last. The fourth order, level order or breadth-first, visits nodes level by level from the root downward, left to right within each level, and uses a queue instead of recursion.

Each order has typical uses. Preorder visits a parent before its children, so it is used to copy a tree, to print a hierarchy with indentation, or to save a tree to a file in a form that can be rebuilt. Inorder visits a binary search tree's keys in sorted order, which lesson 8 relies on. Postorder visits children before their parent, so it is used whenever a node's result depends on its children's results: computing the size or height of every subtree, freeing every node of a tree in C without touching freed memory, and evaluating an expression tree. Level order finds the shallowest node with some property and prints a tree level by level. All four visit each node once, so they cost O(n) time. The depth-first orders use stack space proportional to the height; level order uses queue space proportional to the widest level.

# Traversals of a small binary tree, recursive and level order
from collections import deque

class N:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

root = N(50, N(30, N(20), N(40)), N(70, N(60), N(80)))

def preorder(n, out):
    if n: out.append(n.key); preorder(n.left, out); preorder(n.right, out)
    return out

def inorder(n, out):
    if n: inorder(n.left, out); out.append(n.key); inorder(n.right, out)
    return out

def postorder(n, out):
    if n: postorder(n.left, out); postorder(n.right, out); out.append(n.key)
    return out

def level_order(n):
    out, q = [], deque([n])
    while q:
        cur = q.popleft()
        out.append(cur.key)
        if cur.left: q.append(cur.left)
        if cur.right: q.append(cur.right)
    return out

def height(n):            # postorder: children first, then the node
    return -1 if n is None else 1 + max(height(n.left), height(n.right))

print("preorder   ", preorder(root, []))
print("inorder    ", inorder(root, []))
print("postorder  ", postorder(root, []))
print("level order", level_order(root))
print("height     ", height(root))

preorder    [50, 30, 20, 40, 70, 60, 80]
inorder     [20, 30, 40, 50, 60, 70, 80]
postorder   [20, 40, 30, 60, 80, 70, 50]
level order [50, 30, 70, 20, 40, 60, 80]
height      2

Expression trees

An arithmetic or logical expression can be stored as a binary tree in which every leaf is an operand and every internal node is an operator applied to its two subtrees. The expression (speed − 5) × 2 + length / 100 has + at the root, the subtree for (speed − 5) × 2 on the left and the subtree for length / 100 on the right. Parentheses disappear, because the shape of the tree records the grouping. The three traversals then produce the three notations: preorder gives prefix notation, + × − speed 5 2 / length 100; postorder gives the postfix notation of lesson 5, speed 5 − 2 × length 100 / +; and inorder gives infix, though it needs parentheses added to be unambiguous. Evaluating the tree is a postorder computation: evaluate both children, then apply the operator.

Decision trees in firmware

The NS-4 classification tree is a binary tree whose internal nodes each hold a test, such as length < 6,000 mm or axles > 2, and whose leaves each hold a class code. Classifying a vehicle walks a single path from the root, going left when the test is true and right when it is false, until it reaches a leaf. The cost is the depth of the leaf reached, at most the height of the tree. Northway's current tree has 31 nodes and height 5, so every vehicle is classified in at most five comparisons, a fixed and tiny worst case that is easy to verify. Because the tree is stored as an array of fixed-size records in flash, a new set of rules is just a new block of data, checked by a CRC before the firmware accepts it.

/* Classification tree stored as an array in flash (NS-4 firmware) */
#include <stdint.h>

typedef struct {
    uint8_t  field;        /* 0 = length_mm, 1 = axles, 2 = speed_dkmh, 0xFF = leaf */
    uint8_t  leaf_class;   /* class code when field == 0xFF                       */
    uint16_t yes, no;      /* indexes of the children                             */
    uint32_t threshold;    /* test is: value < threshold                          */
} ctnode_t;

uint8_t classify(const ctnode_t *tree, const uint32_t v[3])
{
    uint16_t i = 0;                                   /* start at the root */
    for (int steps = 0; steps < 16; steps++) {        /* bound: no tree is deeper than 16 */
        const ctnode_t *n = &tree[i];
        if (n->field == 0xFF) return n->leaf_class;
        i = (v[n->field] < n->threshold) ? n->yes : n->no;
    }
    return 0;                                         /* malformed tree: unknown class */
}