A perfect binary tree is a binary tree in which every internal node has two children and all leaves sit at the same depth. This makes its structure symmetrical. section 1.4.4
The structural variations differ in what they require:
- A binary tree limits each parent to at most two children. section 1.4.4
- A full binary tree gives every node either zero or two children. section 1.4.4
- A perfect binary tree combines two children at each internal node with leaves aligned at the same depth. 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 the three diagrams to see how the perfect tree adds uniform leaf depth to the binary-tree constraints. section 1.4.4
