liveBook · Manning

Perfect binary tree

As explained in Algorithms Every Programmer Should Know

A perfect binary tree is a binary tree whose internal nodes have two children and whose leaves all occur at the same depth.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the structure and distinguishes it from binary and full binary trees, without deriving search complexity.
Examples
Contrasts diagrams of binary, full, and perfect tree structures.
What it assumes
Defines binary trees, nodes, leaves, and depth while explaining the perfect-tree conditions.
What you can do after
Understand it by distinguishing its child and leaf-depth conditions from other binary tree types.
How it connects
Connects perfect binary trees to binary trees, full binary trees, tree depth, and breadth-first and depth-first search.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.