COMP 210: Data Structures

Implementing a Complete Binary Tree as an Array

Complete Binary Trees: The Array Trick

A complete binary tree can be implemented using a simple array, with no Node class and no pointers necessary to get to the left and right children. The data values are stored contiguously in the array, and we calculate the indices of the left child and right child’s data using a simple formula.

For any node located at index i in the array:

• Left Child: Located at index 2i + 1

• Right Child: Located at index 2i + 2

We can even calculate the location of a parent node, again without any pointers.

• Parent: Located at index floor((i − 1)/2) (stated mathematically as ⌊(i − 1)/2⌋)

This array-based implementation is highly memory efficient, saving the overhead of storing node references.