A scheme for storing binary trees in an array X is as follows. Indexing of X…

Concept: in this 1-indexed array representation, a node at index i places its left child at 2i and its right child at 2i+1. The array must be large enough to hold the largest index that any node of an n-node binary tree can occupy — and since the tree's shape is arbitrary, the required size is fixed by the worst-case (most skewed) shape, not by a balanced or average one.

Application:

1. The root always occupies index 1.

2. At any node with index i, moving to the right child gives index 2i+1, which is always larger than moving to the left child (2i). To maximize the index reached, chase only right children at every step.

3. This produces the index sequence 1, 3, 7, 15, ... where each term satisfies a(k+1) = 2·a(k) + 1.

4. Solving this recurrence (or verifying it by induction), after k right-child moves from the root — i.e. after placing k+1 nodes — the index reached is a(k) = 2(k+1) − 1.

5. So for a chain of n nodes (root + (n−1) right children), the last node lands at index 2n − 1 — the highest index any node of an n-node tree can ever need.

Cross-check: for n = 4 nodes chained purely through right children (A → B → C → D), the indices are 1, 3, 7, 15 = 24 − 1, matching the recurrence exactly. Since no other shape (balanced or otherwise) ever pushes a node past this index, an array of size 2n − 1 is both necessary (for the skewed case) and sufficient (for every other shape).

Result: the minimum size of X is 2n − 1.

Note: log2n and n only suffice for balanced or trivially simple shapes, and 2n + 1 only captures linear growth — none of these bound the exponential growth produced by a fully skewed shape.