Inspiration: CS61BL SU26 Lecture 10, slide 37 "You again…" — storing a heap directly in an array, leaving index 0 empty
The slide hands us three formulas and no justification:
$$ \text{left} = 2k, \qquad \text{right} = 2k+1, \qquad \text{parent} = \lfloor k/2 \rfloor $$
Why are they true? And which hypotheses actually do the work? The formulas are not a property of binary trees in general — they are a product of exactly two conditions: the tree is complete, and the array is filled in level order starting at index 1. The whole point of these notes is to locate precisely where each condition gets spent.
One structural shortcut first: proving the left-child formula proves all three. Right child follows because level order visits siblings consecutively; parent follows by inverting. So the real content is a single counting argument.
Let $T$ be a binary tree, $n = |T|$. Root has depth $0$; write $d(v)$ for depth, $h$ for tree height, $L_d = \{v : d(v) = d\}$, $n_d = |L_d|$.
Path code. For a node $v$, let $s(v) \in \{0,1\}^*$ be the sequence of turns from the root ($0$ = left, $1$ = right). The root gets the empty string $\varepsilon$. Clearly $v \mapsto s(v)$ is injective and $|s(v)| = d(v)$.
Left-to-right order within a level. On $L_d$, define $u \prec v$ iff $s(u) <_{\text{lex}} s(v)$. Since same-level path codes have equal length, lexicographic order = numeric order on the strings read as binary. So define
The definition being unfolded. Level-order traversal orders by depth first, then by $\prec$. So an index is simply (how many nodes come before it) + 1:
$$ \mathrm{idx}(v) \;=\; 1 \;+\; \underbrace{\sum_{i < d(v)} n_i}{\text{whole levels above}} \;+\; \underbrace{\mathrm{pos}(v)}{\text{same level, to the left}} \tag{D} $$
The $+1$ is the 1-indexing offset. By construction $\mathrm{idx} : T \to \{1, \dots, n\}$ is a bijection.
Completeness, stated properly. $T$ is complete iff
(C2) is the formalization of "as far to the left as possible" from the lecture slide. It is easy to skip past and it is load-bearing.