complete binary tree

A binary tree in which every level is full except possibly the last, which is filled from the left with no gaps.

In more detail

The no-gaps shape is what lets a heap live in a plain array: position alone tells you each node's parent and children. Its height is always floor(log2 n). A perfect binary tree is the special case where the last level is full too, holding 2^(h+1) - 1 nodes.

Related terms

Taught in

References