complete binary tree

A complete binary tree is a binary tree in which every level is completely filled except possibly the last, whose nodes are packed as far to the left as possible. The tree fills in top to bottom and left to right, leaving no gaps until the final row.

That gap-free shape lets a complete binary tree map directly onto a contiguous array, with no wasted slots or child pointers. Counting positions from zero, the node at index i has its children at 2i + 1 and 2i + 2, and each non-root node finds its parent at the integer part of (i - 1) / 2, which the diagram below traces onto the array:

A binary tree numbered 0 to 6 flattens in level order into an array, with each node at index i having children at 2i+1 and 2i+2.
One Tree, One Array, Shared Indices

Because the tree stays as shallow as its node count allows, its height grows only with the base-2 logarithm of that count. This compact layout makes the complete binary tree the standard backing for a binary heap, a tree that keeps every parent ordered ahead of its children. The heap is the data structure behind priority queues and the heapsort algorithm. Python’s heapq module, for instance, maintains a binary heap over an ordinary list.

A complete binary tree should not be confused with a full binary tree, where every node has zero or two children, or a perfect binary tree, whose last level is filled as well so that all leaves share the same depth. Every perfect binary tree is both full and complete, but a complete binary tree need not be full or perfect.

The Python heapq Module: Using Heaps and Priority Queues

Tutorial

The Python heapq Module: Using Heaps and Priority Queues

In this step-by-step tutorial, you'll explore the heap and priority queue data structures. You'll learn what kinds of problems heaps and priority queues are useful for and how you can use the Python heapq module to solve them.

intermediate data-structures python stdlib

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated July 28, 2026
Computer Science Glossary Share Feedback