Chapter 8

Trees

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.

8.1 Definitions and Examples

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 ...

Get A Concise Introduction to Data Structures using Java now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.