Course contentsShow
← Computer Science
Lesson 486 of 2,87211. Binary TreesFree lesson

Perfect Binary Trees

Binary trees where all internal nodes have two children and all leaves are at the same level.

Perfect Binary Trees

What you'll learn: You'll discover what makes a binary tree "perfect" and why it represents the most balanced and uniform structure possible.

What Is a Perfect Binary Tree?

A perfect binary tree is a special type of binary tree where:

  1. Every internal node has exactly two children
  2. All leaf nodes are at the same level (the bottom level is completely filled)

Think of it like a perfectly symmetrical family tree where every generation is complete—no missing siblings, and everyone at the youngest generation was born at exactly the same time. No exceptions, no gaps.

Key Characteristics

Since all levels are completely filled, a perfect binary tree with height h has:

  • Exactly 2^(h+1) - 1 total nodes
  • Exactly 2^h leaf nodes at the bottom level
  • The maximum number of nodes possible for its height

For example:

  • Height 0: just the root = 1 node
  • Height 1: root + 2 children = 3 nodes
  • Height 2: 7 nodes total (1+2+4)
  • Height 3: 15 nodes total (1+2+4+8)

Perfect vs Complete vs Full

You've learned about full and complete trees. A perfect tree is the strictest:

  • It's automatically a full tree (all internal nodes have two children)
  • It's automatically a complete tree (all levels filled, no gaps)
  • But most full or complete trees are NOT perfect

Perfect trees are rare in practice because adding even one node breaks the perfection.

Key Takeaway: A perfect binary tree is completely balanced with all internal nodes having two children and all leaves at the same depth—representing the most uniform, symmetrical structure possible.