What Is a Complete Binary Tree? The Property Behind Every Heap

You call heapq.heappush(). The heap stays sorted. You move on with your life. This is fine. But if an interviewer asks you why heaps use arrays instead of node pointers, and why that's O(log n), you need to know about the complete binary tree property. It's two rules. You probably already half-know it. This is the other half.

The Definition Fits in Two Lines

A complete binary tree is a binary tree where every level is fully filled, except possibly the last, which has all nodes placed as far left as possible.

Two constraints:

All levels above the last are full.
The last level fills from left to right, no gaps.

Here's a complete binary tree with five nodes:

Level 0: one node, one slot. Level 1: two nodes, both slots. Level 2: two nodes in the two leftmost slots, right half empty. No gaps on the left. Complete.

Now move node 5 to be the right child of 3 instead:

Level 2 has a node on the right with nothing on the left. That gap breaks it. Not complete.

The test is always the same: read the last level left to right. If you find a filled slot after an empty one, it's not complete.

Full, Perfect, and Complete Are Not the Same Thing

These three terms trip people up constantly, and honestly the naming doesn't help.

Type	Rule
Full	Every node has 0 or 2 children. No node has exactly 1 child.
Perfect	Every level is completely filled. All leaves at the same depth.
Complete	All levels full except possibly the last; last level left-justified.

A perfect tree is always complete. A complete tree is only perfect when its last level is also full. A full tree is independent of both. The five-node example above is full (every node has 0 or 2 children) and complete, but not perfect.

The one to lock in: "complete" does not mean "full." It means "no gaps, left-justified."

When a problem says "complete binary tree," it's telling you about left-fill, not about node degree. These are different things and interviewers absolutely know the difference.

Three binary tree types side by side: full (every node 0 or 2 children), perfect (all levels filled), and complete (last level left-justified with one empty slot shown dashed)

Full, perfect, and complete. Three words that mean three different things, despite what your intuition says.

Left-Justified Means No Null Placeholders

This is where the definition stops being trivia and starts being useful.

A complete binary tree can be stored in a flat array with no null placeholders and no pointer fields.

Given [1, 2, 3, 4, 5], the indices map directly to tree positions:

Index:  0  1  2  3  4
Value: [1, 2, 3, 4, 5]

        1         <- index 0
       / \
      2   3       <- indices 1, 2
     / \
    4   5         <- indices 3, 4

For any node at index i, navigation is arithmetic:

Left child: 2 * i + 1
Right child: 2 * i + 2
Parent: (i - 1) // 2

No left pointer. No right pointer. No heap-allocated node objects. Just array indexing. The CPU goes brrrr.

This works because left-justification guarantees no holes. A gap anywhere in the last level would force a null at that index to preserve the math, and your array would have slots with no corresponding nodes.

This is exactly why heaps use arrays. A min-heap is a complete binary tree with one extra rule: every parent is smaller than its children. Insert appends to the array and bubbles up. Extract-min swaps the root with the last element, shrinks the array by one, and bubbles down. Both operations touch the rightmost position of the last level, which is just the end of the array.

The heap data structure is a complete binary tree wearing a constraint. That's the whole secret.

"I don't know, I just copied it from Arcane Overflow and it works" is fine for production. Less fine when the interviewer asks you to explain it.

Complete Binary Tree Height Is Always O(log n)

A complete binary tree with n nodes has height floor(log₂(n)).

At height h, a perfect binary tree has exactly 2^(h+1) - 1 nodes. A complete tree at the same height has between 2^h (only the leftmost node of the last level exists) and 2^(h+1) - 1 (last level also full) nodes. Either way, height is at most log₂(n).

Any algorithm that traverses root to leaf runs in O(log n). Recursive operations use O(log n) call stack depth, not O(n) like a linked list.

When an interviewer asks about the space complexity of recursing over a heap, the answer is O(log n), and the reason is the complete tree guarantee. A general binary tree can degenerate into a linked list with height n. A complete binary tree gets O(log n) for free from the fill rule alone. No balancing needed, no rotation logic, just the shape.

Checking Completeness: BFS With a Flag

If you're given a node-based binary tree and need to verify completeness, BFS is the right tool. The idea: once you see a node missing a child, every subsequent node in the traversal must be a leaf.

from collections import deque

def is_complete(root):
    if not root:
        return True
    
    queue = deque([root])
    found_incomplete = False
    
    while queue:
        node = queue.popleft()
        
        if node.left:
            if found_incomplete:
                return False
            queue.append(node.left)
        else:
            found_incomplete = True
        
        if node.right:
            if found_incomplete:
                return False
            queue.append(node.right)
        else:
            found_incomplete = True
    
    return True

The flag trips as soon as we hit a node with a missing child. After that, any non-null child is a gap after an empty slot, which violates the property. O(n) time, O(w) space where w is the maximum width.

BFS is the natural fit because completeness is a level-by-level property. DFS works too, but you'd have to track depth and position, which is messier. Pick the tool that matches the shape of the constraint.

The Interview Problem That Rewards You for Knowing This

LeetCode 222, "Count Complete Tree Nodes," is the canonical example. The brute-force is O(n): visit every node and count. Knowing the structure gives you O(log²n).

From any subtree root, measure the leftmost depth and the rightmost depth. If they're equal, the subtree is a perfect binary tree and you can count its nodes with 2^h - 1 in constant time. If they differ, recurse into both subtrees.

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left, right = root, root
        left_height = right_height = 0
        
        while left:
            left_height += 1
            left = left.left
        
        while right:
            right_height += 1
            right = right.right
        
        if left_height == right_height:
            return (1 << left_height) - 1
        
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

O(log²n): each call does O(log n) work measuring heights, and the recursion has at most O(log n) levels because at least one branch always resolves to a perfect subtree.

That improvement exists only because the tree is complete. On a general binary tree, equal left and right heights don't imply the subtree is perfect. The guarantee comes from the structure.

Where Else This Shows Up

Segment trees. A segment tree over n elements uses the same array indexing pattern (left = 2*i, right = 2*i + 1, 1-indexed). Most implementations allocate 4n space because the complete tree's last level can hold up to 2n slots depending on alignment. The array representation is borrowed directly from this.

Complexity questions. "What's the height of a heap with n elements?" O(log n), because it's a complete binary tree. "What's the call stack depth when you recurse over a heap?" O(log n), same reason. The top heap interview problems almost all hinge on this bound. Knowing the definition lets you answer a whole category of questions that otherwise feel like memorization.

Serialization. LeetCode's internal tree format uses level-order with nulls for missing nodes. Understanding the complete binary tree's array representation helps you reason about where nulls go and how to reconstruct trees from level-order input. The binary tree traversal patterns all interact with this.

The complete binary tree property isn't background knowledge. It's the reason heaps are O(log n), the reason array indexing replaces pointers, and the reason LeetCode 222 has a sub-linear solution. Once you see it, you see it everywhere.

If you want to practice explaining this under real interview pressure, SpaceComplexity runs voice-based mock interviews on heap and tree problems with rubric-based feedback, so you can say "this tree is complete, height is O(log n)" out loud before you need to say it live.