A binary tree is a hierarchy in which each parent has at most two children, called the left and right nodes. Every node descends from a root; nodes with no children are leaves. section 1.4.4
Tree forms add different limits on how children and leaves are arranged:
- A binary tree allows up to two children per parent. 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 all leaves at the same depth. section 1.4.4
To explore a tree, breadth-first search (BFS) visits layer by layer, while depth-first search (DFS) follows a path toward a leaf before backtracking. A FIFO queue supports BFS; a LIFO stack supports DFS. Both take O(V) time, with space bounded by tree width for BFS and depth for DFS. section 1.4.4 section 1.5
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 ordinary, full, and perfect binary tree shapes side by side. section 1.4.4






