Course contentsShow
← Mathematics
Lesson 2671 of 3,12153. Graph TheoryFree lesson

Binary Trees and Complete Trees

Explore binary trees, full binary trees, complete binary trees, and their properties.

Binary Trees and Complete Trees

What you'll learn: You'll discover the special structure of binary trees, understand what makes a tree "full" or "complete," and learn the key properties that make these structures so powerful in mathematics and computing.

What Makes a Tree Binary?

A binary tree is a rooted tree where every vertex has at most two children. We typically label these children as the left child and right child. Think of a family tree where each person has at most two direct descendants—this naturally forms a binary structure.

Unlike general rooted trees (where a vertex might have 3, 4, or any number of children), binary trees impose this strict limit of two, creating a predictable, symmetric structure.

Full Binary Trees

A full binary tree (also called a strictly binary tree) is one where every internal vertex has exactly two children—no vertex has just one child. It's "all or nothing": each vertex either has two children or is a leaf (has zero children).

Property: If a full binary tree has i internal vertices, it has exactly i + 1 leaves and 2i + 1 total vertices.

Complete Binary Trees

A complete binary tree is a binary tree where:

  • Every level is completely filled except possibly the last
  • The last level has all its vertices as far left as possible

Imagine filling seats in a theater row-by-row from left to right—you finish each row before moving to the next, and if the last row isn't full, people sit leftmost first. Complete binary trees have this "packed" structure, which makes them extremely efficient for array-based storage.

Property: A complete binary tree with n vertices has height ⌊log₂(n)⌋.

Key Takeaway: Binary trees restrict vertices to at most two children; full binary trees require internal vertices to have exactly two children; complete binary trees pack vertices level-by-level left-to-right, creating optimal height-to-vertex ratios perfect for efficient algorithms.