DSA Trees

Array Implementation of Trees

A priority queue for n = 10⁷ pending jobs needs parent and child hops without chasing heap pointers across the heap. Store the tree in an array and recover links with : that is the behind every binary heap.

The representation stays compact only while the shape is a . A turns “no pointers” into exponential empty slots.

What happens first?

Check the shape

Complete / near-complete, or full of holes?

Pick a base

0-based or 1-based formulas; stay consistent.

Parent/child from i; reject the root parent case.

Mutate carefully

Append preserves completeness; middle deletes usually do not.

What actually happens

Naive idea: allocate a node object with left/right pointers for every heap entry. Navigation works, but each node carries reference overhead and poor locality under heavy sift-up / sift-down traffic.

Break: at n = 10⁷, pointer-heavy nodes waste memory bandwidth. Worse, if you force an implicit array onto a right-only chain of height 30, the array span is about 2³¹ − 1 slots for only 31 real nodes.

Better idea: require a (), store values in , and navigate with formulas. Append inserts at the next level-order index; heaps then restore value order in O(log n).

What must never become false

For a dense complete-tree wrapper, occupied positions are exactly 0 .. size − 1. Parent/child formulas are valid only for occupied indices, and the root has no parent. Deleting a middle slot without repairing completeness silently falsifies the representation.

How to choose an array tree

1. Is the tree complete (or nearly so)? Heaps, tournament trees, and many segment-tree layouts fit. Arbitrary BSTs usually do not.

2. Do you need fast subtree rewires? Linked nodes can re-parent with a few pointer writes. Implicit arrays may relocate large ranges.

3. Will absence collide with payloads? Reserve null/None as empty-slot markers only if values cannot be null, or use an explicit occupancy set.

Quantitative check

Complete tree: n = 10⁷ nodes need 10⁷ slots. Right-only chain of height 24 needs only 25 nodes but an array span of 2²⁵ − 1 ≈ 3.4 × 10⁷ positions. Shape, not node count, decides whether the implicit array is viable.

Shape determines whether the representation is compact

Select a shape and inspect its occupied slots. The tree edges do not change when you switch index conventions; only the labels and formulas do.

Tree shape and representation explorer

Change the shape, then compare the pointer view with its implicit level-order array.

Complete

Every level except possibly the last is full; the last level is filled from left to right.

full: No
complete: Yes
perfect: No
height Balanced: Yes

Implicit array

6 values · 6 allocated positions · 100% occupied · height 2

Ai=0

Bi=1

Ci=2

Di=3

Ei=4

Fi=5

0-based: left = 2i + 1 · right = 2i + 2 · parent = floor((i - 1) / 2)

Index formulas

Zero-based and one-based implicit binary tree formulas
Relationship	0-based array	1-based array	Precondition
Root	0	1	Tree is non-empty.
Left child	2i + 1	2i	Computed position must be occupied.
Right child	2i + 2	2i + 1	Computed position must be occupied.
Parent	⌊(i − 1) / 2⌋	⌊i / 2⌋	The root has no parent.
Depth	⌊log₂(i + 1)⌋	⌊log₂(i)⌋	Position is positive after adjusting for the base.
Indices at depth d	2ᵈ − 1 … 2ᵈ⁺¹ − 2	2ᵈ … 2ᵈ⁺¹ − 1	These are possible positions, not necessarily occupied ones.

Root trap: the parent formula is valid only for a non-root node. In Python, applying it to index 0 gives −1 and may accidentally read the last element; in Java, integer division of −1 by 2 gives 0. Check the root explicitly.

A bounds-safe complete-tree wrapper

For a dense complete tree, valid positions are exactly 0..size−1. Appending inserts at the next level-order position. These examples reject null/None payloads so absence is unambiguous.

Python

python

class CompleteArrayTree:
    def __init__(self):
        self.values = []

    def add_level_order(self, value):
        if value is None:
            raise ValueError("None is reserved for absence")
        self.values.append(value)
        return len(self.values) - 1

    def _require_index(self, index):
        if index < 0 or index >= len(self.values):
            raise IndexError("node index out of range")

    def parent_index(self, index):
        self._require_index(index)
        return None if index == 0 else (index - 1) // 2

    def left_index(self, index):
        self._require_index(index)
        child = 2 * index + 1
        return child if child < len(self.values) else None

    def right_index(self, index):
        self._require_index(index)
        child = 2 * index + 2
        return child if child < len(self.values) else None

tree = CompleteArrayTree()
for value in "ABCDEFG":
    tree.add_level_order(value)

i = 1  # B
print(tree.values[tree.left_index(i)])   # D
print(tree.values[tree.right_index(i)])  # E

Java

java

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.OptionalInt;

final class CompleteArrayTree<T> {
    private final List<T> values = new ArrayList<>();

    int addLevelOrder(T value) {
        values.add(Objects.requireNonNull(value, "null is reserved for absence"));
        return values.size() - 1;
    }

    T valueAt(int index) {
        requireIndex(index);
        return values.get(index);
    }

    OptionalInt parentIndex(int index) {
        requireIndex(index);
        return index == 0 ? OptionalInt.empty()
                          : OptionalInt.of((index - 1) / 2);
    }

    OptionalInt leftIndex(int index) {
        requireIndex(index);
        long child = 2L * index + 1; // long avoids intermediate int overflow
        return child < values.size() ? OptionalInt.of((int) child)
                                     : OptionalInt.empty();
    }

    OptionalInt rightIndex(int index) {
        requireIndex(index);
        long child = 2L * index + 2;
        return child < values.size() ? OptionalInt.of((int) child)
                                     : OptionalInt.empty();
    }

    private void requireIndex(int index) {
        if (index < 0 || index >= values.size()) {
            throw new IndexOutOfBoundsException("node index: " + index);
        }
    }

    public static void main(String[] args) {
        CompleteArrayTree<Character> tree = new CompleteArrayTree<>();
        for (char value : "ABCDEFG".toCharArray()) tree.addLevelOrder(value);

        int i = 1; // B
        System.out.println(tree.valueAt(tree.leftIndex(i).orElseThrow()));  // D
        System.out.println(tree.valueAt(tree.rightIndex(i).orElseThrow())); // E
    }
}

Why complete trees fit and sparse trees do not

Complete tree: Θ(n) slots

Level order is contiguous, so n nodes occupy exactly n array positions. Parent and child navigation needs no references, and nearby levels tend to have good cache locality.

Right chain: exponential span

A right-only chain of height h lands at indices 0, 2, 6, 14, …. Storing only h + 1 nodes requires an array span of 2^h+1 − 1 positions.

Tradeoffs between implicit arrays and linked nodes
Concern	Implicit array	Linked nodes
Navigation	O(1) index arithmetic	O(1) reference follow
Memory locality	Usually contiguous and cache-friendly	Nodes may be scattered; each stores references
Arbitrary sparse shape	Holes may dominate storage	Allocates only actual nodes
Move a subtree	May relocate many values or require a sparse map	Can rewire a constant number of links once nodes are known
Grow a complete tree	Append in amortized O(1)	Must locate the next level-order parent unless tracked

Operations and mutation semantics

Navigate

Parent or child index calculation is O(1), followed by a bounds and occupancy check.

Traverse

Scanning a dense array is already breadth-first order: Θ(n) time and O(1) traversal state.

Insert

Appending preserves completeness in amortized O(1). A heap then restores heap order in O(log n).

Delete

Removing the last node is O(1). Arbitrary deletion usually swaps in the last value, then repairs the application invariant.

Failure modes

Using the parent formula for the root.
Treating “index is in bounds” as “a node exists” in a sparse representation.
Using null both as a valid payload and as an empty-slot marker.
Letting 2i + 2 overflow before checking the array bound.
Deleting a middle slot and silently breaking the completeness invariant.

Good fits

Binary heaps: complete shape plus heap order.
Tournament trees: internal positions summarize child winners.
Segment trees: layouts trade simple arithmetic for bounded extra capacity.
Static complete decision trees: predictable positions and compact traversal.

Exercises

For a 0-based complete tree of size 7, list parent, left, and right of index 2. What fails if you apply the parent formula at index 0 in Python without a root check?
Height-20 right chain: how many real nodes vs array span? When would you switch to linked nodes?
Design a delete that removes index i from a complete array tree while restoring the completeness invariant. What value moves, and what application invariant (for example heap order) must be repaired next?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): heaps and heap-sort array indexing.
Weiss, Data Structures and Algorithm Analysis: binary heaps as complete trees in arrays.
Segment tree / binary heap lecture notes that contrast 0-based vs 1-based layouts.

Takeaway

Implicit array trees trade pointers for index arithmetic. They shine on complete shapes (heaps, many segment layouts) and collapse under sparse holes. Keep the completeness invariant explicit whenever you mutate.