A tree organizes data hierarchically, like a file system or corporate org chart. It has one root; every other node descends from it, with edges flowing downward and no loops. Nodes without children are leaves. section 1.4.4 section 1.5
Structural constraints define common tree types:
- A binary tree gives each node at most two children. section 1.4.4
- A full binary tree gives each node either zero or two children. section 1.4.4
- A perfect binary tree has leaves at the same depth. section 1.4.4
To visit nodes, breadth-first search (BFS) explores level by level using a FIFO queue; depth-first search (DFS) follows a branch before backtracking, using a LIFO stack. Both take O(V) time; BFS space depends on tree width, while DFS space depends on depth. section 1.5 section 1.4.4
Figure 1.8 A comparison of common binary tree structural variations. Left: A standard binary tree where nodes have a maximum of two children. Middle: A full binary tree enforcing that nodes possess either exactly zero or exactly two child nodes. Right: A highly uniform perfect binary tree where all interior nodes contain two children and every leaf node aligns at the exact same depth level.
Compare binary, full, and perfect tree shapes. section 1.4.4
Figure 1.9 The two fundamental strategies for searching non-linear data structures. Left: Depth-First Search (DFS) goes deep down a single path to a leaf node. Right: Breadt-First Search (BFS) expands outward, exploring all the neighboring nodes layer by layer before descending to the next level.
See how depth-first and breadth-first search explore a tree differently. section 1.5













