Complete Binary Tree in Data Structures (DSA)

Introduction

In Data Structures, trees come in many forms, but Complete Binary Tree (CBT) is one of the most important and practical ones.
You cannot understand Heap, Priority Queue, or Heap Sort properly without first understanding the Complete Binary Tree.

This blog explains CBT from scratch, with clear rules, examples, diagrams, and interview-ready logic.

---

What is a Binary Tree?

A Binary Tree is a tree data structure in which:

• Each node has at most two children

  • Left child

  • Right child

Example:

    A
   / \
  B   C

---

What is a Complete Binary Tree?

A Complete Binary Tree is a special type of binary tree that follows two strict rules.

✅ Rule 1: All levels must be completely filled

Except possibly the last level.

✅ Rule 2: Last level must be filled from LEFT to RIGHT

• No gaps allowed

• You cannot skip a left child and add a right child

---

Simple Definition (Interview-Ready)

A Complete Binary Tree is a binary tree in which all levels are fully filled except possibly the last level, and the last level is filled from left to right.

---

Valid Complete Binary Tree Examples

Example 1

        1
       / \
      2   3
     / \
    4   5

✔ All upper levels filled
✔ Last level filled from left
✔ This is a Complete Binary Tree

---

Example 2

        1
       / \
      2   3
     /
    4

✔ Last level partially filled
✔ Node is on the left side
✔ Still a Complete Binary Tree

---

❌ Invalid Complete Binary Tree Examples

Example 1 (Gap on the left)

        1
       / \
      2   3
       \
        5

❌ Left child missing
❌ Right child exists
❌ Not a Complete Binary Tree

---

Example 2 (Right filled before left)

        1
       / \
      2   3
         /
        6

❌ Left side empty first
❌ Violates left-to-right rule

---

Why “Complete” is Important?

The word complete refers to the shape of the tree, not the values.

CBT ensures:

• No wasted space

• Predictable structure

• Easy array storage

---

Array Representation of Complete Binary Tree

A Complete Binary Tree can be stored perfectly in an array without gaps.

Example Tree

        10
       /  \
      20   30
     / \
    40  50

Array Representation (0-based indexing)

Index:  0   1   2   3   4
Value: [10, 20, 30, 40, 50]

✔ No empty index
✔ Continuous memory
✔ Very efficient

---

Index Formula (0-Based Indexing)

If a node is at index i:

👉 These formulas work only because the tree is complete.

---

Why These Formulas Work (Core Logic)

• Nodes are stored level by level

• Each node has 2 child positions

• No gaps exist

That’s why:

• Children positions grow as 2*i

• Parent position shrinks as (i-1)/2

---

Complete Binary Tree vs Other Trees

CBT vs Full Binary Tree

---

CBT vs Perfect Binary Tree

---

Real-Life Use of Complete Binary Tree

• 🔹 Heap (Min Heap & Max Heap)

• 🔹 Priority Queue

• 🔹 CPU Scheduling

• 🔹 Heap Sort

• 🔹 Memory-efficient tree storage

---

Common Interview Questions

Q1. Is every Complete Binary Tree a Heap?
❌ No. Heap also requires heap property.

Q2. Why Heap uses CBT?
✔ Efficient array storage
✔ Faster insertion & deletion

Q3. Can CBT have missing nodes?
✔ Yes, but only on the last level and only on the right side

---

Key Points to Remember

• ✔ Shape matters, not values

• ✔ Left-to-right filling is mandatory

• ✔ CBT enables array-based trees

• ❌ Right child without left child is illegal

---

One-Line Summary

A Complete Binary Tree is a binary tree filled level by level from left to right, allowing no gaps except at the end of the last level.