tree
A tree is the first big jump away from linear structures. Where an array or a linked list lays things out in a single line, a tree branches: every element (called a node) can point to several others below it. This naturally models hierarchy — a file system, an organization chart, the moves in a game — anything that fans out from a single starting point.
The vocabulary is worth learning once and reusing forever. The single node at the top is the root. A node that points to others is the parent; the ones it points to are its children. A node with no children is a leaf. The height of the tree is the number of edges on the longest path from the root down to a leaf, and the depth of a node is its distance from the root. Crucially, a tree has no cycles: you can never follow children and end up back where you started, and every node except the root has exactly one parent.
Trees matter because their branching shape can make operations fast. If a tree stays bushy and shallow rather than long and stringy, you can reach any node in roughly O(log n) steps instead of O(n) — the same logarithmic payoff that makes binary search fast. Most of the structures in this section (search trees, heaps, tries) are special trees engineered to keep that shape and guarantee that speed.
// (1) <- root
// / \
// (2) (3)
// / \
// (4) (5) <- leaves
struct Node {
int value;
Node* left;
Node* right;
};A small tree drawn with the root on top, and the matching node struct.
Trees are drawn upside down in computer science: the root sits at the top and the leaves at the bottom.