Chapter 8

Trees are non-linear, hierarchical, and recursive data structures with a wide range of applications. In fact, we have already seen call trees in Section 7.2 as a useful model for tracking recursive computations.

A tree is a (possibly empty) set of elements called nodes with one node designated as the root. The root is connected via edges to some number of child nodes, each of which is itself the root of a subtree. Thus, trees are naturally recursive. A leaf is a node with no children; an internal node is any non-leaf. A branch in a tree is a path of connected edges starting at the root and ending in a leaf. Trees are usually drawn with the root at the top.

For example, in the tree below, 31 is the ...

Start Free Trial

No credit card required