How is a binary tree stored in an array, and how are a node's children and parent found?

Each node is stored at the index given by its rank: the root has rank 1, the left child of the node at $k$ has rank $2k$, the right child $2k + 1$. The parent of the node at $k$ is therefore at $\lfloor k/2 \rfloor$. Index 0 is left empty.

* The rank of each node is its array index; the gaps at 8 and 9 are E's missing children. *

$$\text{rank}(\text{root}) = 1 \qquad \text{rank}(\text{left child}) = 2 \cdot \text{rank}(\text{parent}) \qquad \text{rank}(\text{right child}) = 2 \cdot \text{rank}(\text{parent}) + 1$$

No references are stored at all. The tree structure is encoded entirely in the index arithmetic:

• children of $k$: $2k$ and $2k + 1$
• parent of $k$: $k // 2$ (integer division), since both $2k$ and $2k+1$ divide back down to $k$
• $k$ is a left child when $k$ is even, a right child when $k$ is odd

In the example, F sits at 5, so its children G and H sit at 10 and 11, and both have parent $10 // 2 = 11 // 2 = 5$.

Why start at 1? With the root at index 1 the formulas are the clean $2k$ and $2k+1$. Starting at 0 also works, but the formulas become $2k + 1$, $2k + 2$ and $(k-1) // 2$, which are easier to get wrong.

Go deeper:

• Binary heap — heap implementation — the most important real use of this layout, with the same index formulas.