Complete Binary Tree — Definition, Formula & Examples

A complete binary tree is a binary tree in which every level is completely filled with nodes, except possibly the last level, where all nodes are packed as far left as possible.

A binary tree of height $h$ is complete if all levels $0, 1, \ldots, h-1$ contain exactly $2^k$ nodes at level $k$ , and all nodes at level $h$ occupy the leftmost positions without gaps.

Key Formula

n \leq 2^{h+1} - 1

Where:

$n$ = Total number of nodes in the complete binary tree
$h$ = Height of the tree (number of edges on the longest root-to-leaf path)

How It Works

To check whether a binary tree is complete, examine it level by level from top to bottom. Every level above the last must have exactly the maximum number of nodes (each internal node has two children). On the last level, nodes must fill in from left to right with no empty positions before an occupied one. This left-to-right filling property is precisely what allows a complete binary tree to be stored efficiently in an array: the node at index

i

has children at indices

2i+1

and

2i+2

Worked Example

Problem: A complete binary tree has 10 nodes. Determine its height and verify the array layout of the last level.

Step 1: Find the height. A complete binary tree with

n

nodes has height

h = \lfloor \log_2 n \rfloor

h = \lfloor \log_2 10 \rfloor = \lfloor 3.32 \rfloor = 3

Step 2: Count nodes in levels 0 through 2 (the fully filled levels). Level

k

has

2^k

nodes.

2^0 + 2^1 + 2^2 = 1 + 2 + 4 = 7

Step 3: The remaining nodes sit on level 3, filled left to right.

10 - 7 = 3 \text{ nodes on level 3 (out of a maximum of } 2^3 = 8\text{)}

Answer: The tree has height 3, with levels 0–2 fully occupied (7 nodes) and 3 nodes packed to the left on level 3. In a zero-indexed array of length 10, these last-level nodes occupy indices 7, 8, and 9.

Why It Matters

Binary heaps, the backbone of priority queues and heap sort, rely on the complete binary tree structure to guarantee

O(\log n)

insertion and extraction. The array representation eliminates pointer overhead, making heaps cache-friendly and memory-efficient in practice.

Common Mistakes

Mistake: Confusing a complete binary tree with a full binary tree.

Correction: A full binary tree requires every node to have either 0 or 2 children, but it does not require left-to-right filling on the last level. A complete binary tree allows the last level to be partially filled, provided nodes are contiguous from the left.