Course contentsShow
← Computer Science
Lesson 461 of 2,87211. Binary TreesFree lesson

Array-Based Complete Binary Trees

Represent complete binary trees in contiguous arrays using index arithmetic for parent-child relationships.

Array-Based Complete Binary Trees

What you'll learn: How to store a complete binary tree efficiently in a contiguous array without using pointers, using simple index arithmetic to navigate parent-child relationships.

Why Use an Array?

Instead of creating nodes with left and right pointers, you can represent a complete binary tree directly in an array. Remember, a complete binary tree fills all levels from left to right without gaps (except possibly the last level). This predictable structure allows us to use clever index math to find relationships.

The Storage Pattern

Store the tree level-by-level, left to right, starting at index 0 (or 1, depending on convention):

  • Root goes at index 0
  • Next level: indices 1, 2
  • Next level: indices 3, 4, 5, 6
  • And so on...

Example tree stored in an array:

Tree:        10
           /    \
          20    30
         /  \   /
        40  50 60

Array: [10, 20, 30, 40, 50, 60]

Index Arithmetic (0-based indexing)

For any node at index i:

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

Example: Node 20 is at index 1. Its left child is at 2*1 + 1 = 3 (value 40), and its parent is at (1-1)/2 = 0 (value 10).

Why This Works

Because complete binary trees have no gaps, every position in the array corresponds to exactly one tree position. You never waste space with "holes," and pointer overhead disappears—just pure data in contiguous memory.

Key Takeaway: Array-based representation of complete binary trees uses index arithmetic (2*i+1, 2*i+2, (i-1)/2) to efficiently navigate parent-child relationships without pointers, perfect for heaps and priority queues.