Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Eytzinger arrays: store a search tree in breadth-first order

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An Eytzinger array stores a binary search tree in breadth-first order. For a slot at index i, its children occupy 2i+1 and 2i+2 when those positions exist. This static catalog starts from unique sorted case IDs, fills the implicit tree by an in-order walk, and stores each key's rank in the original sorted sequence. A lower-bound query remembers the best key at or above the target while following one comparison path. It returns both the key and rank, or None if no qualifying ID exists. Duplicates are removed at construction; an application that needs duplicate records must define a composite key or maintain a separate posting list. The layout cannot accept a sorted append without rebuilding its implicit child positions.

Operational case

A dispatch system loads case IDs 19, 29, 47, 61, 83, and 103 from a morning snapshot. The stored breadth-first layout begins with 61, then 29 and 103; it is not numerically sorted in memory. Searching for the first ID at or after 52 returns 61 at sorted rank three. A lookup for 104 returns None. An equality query for 61 is true even though the key appears at array slot zero. If a writer appends 127 to the layout as if it were a sorted array, the child arithmetic no longer represents a search tree, so this index must be rebuilt from a new immutable snapshot.

Working Python program

python
class EytzingerCaseCatalog:
    def __init__(self, case_ids):
        ordered = sorted(set(case_ids))
        self.layout = [None] * len(ordered)
        self.ranks = [None] * len(ordered)
        cursor = 0

        def place(index):
            nonlocal cursor
            if index >= len(ordered):
                return
            place(2 * index + 1)
            self.layout[index] = ordered[cursor]
            self.ranks[index] = cursor
            cursor += 1
            place(2 * index + 2)

        place(0)

    def lower_bound(self, case_id):
        index, best = 0, None
        while index < len(self.layout):
            if self.layout[index] >= case_id:
                best = index
                index = 2 * index + 1
            else:
                index = 2 * index + 2
        return None if best is None else (self.layout[best], self.ranks[best])

    def contains(self, case_id):
        result = self.lower_bound(case_id)
        return result is not None and result[0] == case_id


catalog = EytzingerCaseCatalog([83, 19, 61, 47, 19, 103, 29])
print(catalog.layout)
print(catalog.lower_bound(52), catalog.contains(61), catalog.lower_bound(104))

Output

Output
[61, 29, 103, 19, 47, 83]
(61, 3) True None

Time, space, and tradeoff

Building the layout visits each of N unique keys once after sorting, so the implementation costs O(N log N) including sorting and O(N) extra storage for keys and ranks. A lower-bound walk uses O(log N) comparisons because the implicit tree has logarithmic height; it uses O(1) query memory. This lesson does not claim a measured cache advantage in Python. Branch prediction, prefetch behavior, element width, and the host language can change the performance comparison with ordinary binary search. The representation helps when repeated reads dominate and updates arrive as occasional snapshots. The rank array is an explicit convenience and doubles per-slot metadata relative to a keys-only layout.

Common Mistakes

  • Do not use a standard bisect call on the breadth-first array.
  • Do not append a key without rebuilding the layout.
  • Do not confuse the layout slot with the sorted rank.
  • Do not promise a cache-speed gain without measuring the actual runtime.

Connected lessons

Compare its update and query contract with Cartesian trees: preserve sequence order under a heap minimum, Leftist heaps: keep the right spine short for meld, Potential disjoint sets: preserve numeric differences across merges, then complete the structure audit and decision quiz.

Piecewise interpolation indexes: predict a bounded rank window adds a distinct structure contract to compare.

data structures
array-data-structure-guide
Storage details