Array representation of binary trees

A complete binary tree has a particularly convenient array layout. Store nodes by level order, left to right. With zero-based indexing, the root is index 0, the left child of index i is 2*i + 1, and the right child is 2*i + 2. The parent of any index i > 0 is (i - 1) / 2 using integer division.

Example

The binary tree with A at the root, B and C below, and D and E as B’s children can be stored as [A, B, C, D, E]. B has index 1, so its children have indexes 3 and 4. C has index 2, and its left position would be index 5, outside the five-element array.

Why the formulas work

Each complete level has twice as many positions as the previous one. Numbering positions breadth-first places each pair of children after all earlier parents’ children. If you switch to one-based indexing, the formulas change to left 2*i and right 2*i + 1; never mix these conventions.

C#

C# | ArrayTree.cs

using System.Collections.Generic;
static bool TryLeft<T>(IReadOnlyList<T> values, int index, out T child)
{
    long left = 2L * index + 1;
    if (index >= 0 && left < values.Count)
    {
        child = values[(int)left];
        return true;
    }
    child = default!;
    return false;
}

C++

C++ | ArrayTree.cpp

#include <vector>
#include <cstddef>

template<class T>
bool tryLeft(const std::vector<T>& values, std::size_t i, T& child) {
    if (i >= values.size() || i > (values.size() - 1) / 2) return false;
    std::size_t left = 2 * i + 1;
    if (left >= values.size()) return false;
    child = values[left];
    return true;
}

Constraints and costs

Reading an existing child index is O(1). Traversing n nodes still requires O(n) time. The array itself uses O(n) storage. For arbitrary sparse trees, child positions may be absent; either use explicit empty slots or a linked-node representation. Do not remove placeholders in the middle of a positional array without remapping all descendant indexes.

Common mistake: calculating 2*i+2 using a signed int can overflow for a very large index. Validate bounds before indexing and use a suitable integer type. The example checks candidate indexes against the collection length, but still assumes a reasonably sized array.

Read binary tree types and level-order traversal.

Reference: W3Schools array implementation.