A tree organizes information like a branching hierarchy: one starting node leads to paths that split into smaller paths. Unlike a linked list’s single line, a tree can represent choices, categories, and other relationships without cycles. section 11.1 section 11.3
Trees are recursive data structures made of nodes. Each node stores a value and links to children, while each child begins a valid subtree. The starting node is the root; nodes without children are leaves. A tree may be binary, ternary, or n-ary, depending on how many children its nodes can have. section 11.20 section 11.0
Use a tree when relationships branch rather than form one fixed sequence:
- Represent hierarchies and paths that branch from shared starting points. section 11.1
- Choose a binary tree when each node has at most two children; label those links left and right. section 11.20
- Use specialized trees for tasks such as priority queues, database storage, multidimensional indexing, or classification. section 11.5
- Remember that a formal graph-theoretic tree is connected, undirected, and acyclic, with n vertices and n−1 edges. section 13.7
A branching breakfast
A routine cereal breakfast follows one linear sequence and fits a linked list. A morning that may add sugar, skip cereal, or jump to ice cream creates alternatives and fits a tree much better. section 11.3
Table 11.1 A comparison between linked lists and trees (view table figure)
| Linked list |
Tree |
|---|---|
| A single node has no predecessor (the head). |
A single node has no parent (the root). |
| A single node has no successor (the tail). |
Many nodes don’t have children (the leaves). |
| Each node has exactly one outgoing link to its successor. |
Each node has zero, one, or many links to its children. |
| Doubly linked lists: each node has exactly one link to its predecessor. |
In some trees, nodes have links to their parents. If they do, each node has exactly one link to its only parent. |
Compare linked lists and trees by their starting nodes, endpoints, and numbers of outgoing links. section 11.3
