Trees and traversal

Overview

Introduces tree terminology and the three depth-first traversals.

A tree is a set of nodes with one root and no cycles, where every non-root node has exactly one parent. Depth, height and subtree are the terms you will use most.

Pre-order, in-order and post-order traversals differ only in when a node is visited relative to its children; each is a two-line recursive routine.