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

Complete Binary Trees

Binary trees filled left-to-right at each level except possibly the last; heap structure and array representation.

Complete Binary Trees

You'll learn what makes a binary tree "complete" and why this special structure is perfect for efficient array storage.

What Makes a Tree Complete?

A complete binary tree is a binary tree where every level is completely filled, except possibly the last level — and the last level must be filled from left to right with no gaps.

Think of it like filling seats in a theater: you fill each row completely before moving to the next, and on the last row, everyone sits as far left as possible with no empty seats between people.

The Complete Tree Rules

  1. All levels full except possibly the last: Levels 0 through h-1 must be entirely full
  2. Last level fills left-to-right: Nodes on the bottom level must be as far left as possible, with no gaps

Examples:

  • ✅ Complete: Root with left and right children, left child has left child only
  • ❌ Not complete: Root with left and right children, right child has left child only (gap on left side)
  • ✅ Complete: All nodes filled through level 2, level 3 has nodes only on the left

Why Complete Trees Matter

Complete binary trees have a special superpower: perfect array representation. Because there are no gaps when filling left-to-right, you can store the entire tree in an array without wasting space. Using the formulas you learned earlier (parent at i, children at 2i+1 and 2i+2), every array position is used efficiently.

This property makes complete binary trees the foundation for heaps — a crucial data structure for priority queues and sorting algorithms.

Key Takeaway: A complete binary tree fills all levels top-to-bottom and left-to-right, making it ideal for compact array storage and the basis of heap structures.