Complete Binary Tree: Definition, Example, and Usage

A complete binary tree is a type of binary tree where all levels are fully filled except possibly the last level, which is filled from left to right without gaps. This structure ensures the tree is as compact as possible, making it efficient for storage and operations.

How It Works

A complete binary tree fills each level of the tree completely before moving to the next level. Imagine filling seats in a theater row by row: you fill all seats in the first row, then move to the second, and so on, without leaving empty seats in between.

This means every level except possibly the last is fully occupied, and the last level is filled from left to right without gaps. This property makes the tree very balanced and compact, which is useful for efficient data storage and quick access.

Example

This example shows how to check if a binary tree is complete using a simple level order traversal.

python

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def is_complete_binary_tree(root):
    if not root:
        return True
    queue = deque([root])
    end = False
    while queue:
        current = queue.popleft()
        if current is None:
            end = True
        else:
            if end:
                return False
            queue.append(current.left)
            queue.append(current.right)
    return True

# Example tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

print(is_complete_binary_tree(root))  # Output: True

Output

True

When to Use

Complete binary trees are commonly used in data structures like heaps, which are important for priority queues and efficient sorting algorithms like heapsort. Their compact shape allows easy storage in arrays without wasted space.

Use a complete binary tree when you need a balanced tree that is easy to store and traverse quickly, especially when implementing priority-based data structures or when memory efficiency is important.

Key Points

• All levels except possibly the last are fully filled.
• The last level is filled from left to right without gaps.
• It is more compact and balanced than other binary trees.
• Commonly used in heaps and priority queues.

Key Takeaways

A complete binary tree fills all levels fully except the last, which fills left to right.

It is compact and balanced, making it efficient for storage and access.

Used mainly in heaps and priority queues for fast operations.

Checking completeness can be done with level order traversal.

Its structure allows easy array representation without wasted space.