Tree Array Implementation — Heap Storage Visualized
Store a complete binary tree in a 1-indexed array — parent/child index formulas, interactive visualizer, and heap use cases.
Introduction
Array implementation stores a complete binary tree in a 1-indexed array — no pointers, just index math. Used by binary heaps, segment trees, and priority queues.
Quick index
1. Array layout
Tree: 4
/ \
2 6
/ \ / \
1 3 5 7
Array: [∅, 4, 2, 6, 1, 3, 5, 7]
Index: 0 1 2 3 4 5 6 7Index 0 is unused — root lives at index 1.
2. Interactive visualizer
Tree Array Implementation
Store a complete binary tree in an array — O(1) parent/child via index arithmetic.
1-indexed array
Complete binary tree stored in a 1-indexed array — index 0 unused.
Array representation
// 1-indexed array for complete binary tree const tree = [null, 4, 2, 6, 1, 3, 5, 7] // index 1 = root (4) // index 2 = left child of 4 (2) // index 3 = right child of 4 (6)
No pointers — parent/child computed by index math.
Root index
1
Space
O(n)
Used in
Heaps
3. Full implementation
class ArrayBinaryTree {
constructor(values) {
// 1-indexed: index 0 unused
this.tree = [null, ...values]
}
parent(i) {
return Math.floor(i / 2)
}
left(i) {
return 2 * i
}
right(i) {
return 2 * i + 1
}
get(i) {
return this.tree[i] ?? null
}
set(i, val) {
this.tree[i] = val
}
root() {
return this.tree[1] ?? null
}
height() {
let h = 0
for (let i = this.tree.length - 1; i >= 1; i--) {
if (this.tree[i] != null) {
h = Math.floor(Math.log2(i)) + 1
break
}
}
return h
}
}Function calls with output
// ── Demo calls — output shown on the right ──
const t = new ArrayBinaryTree([4, 2, 6, 1, 3, 5, 7])
t.root() // → 4
t.get(t.left(1)) // → 2 (left child of root)
t.get(t.right(1)) // → 6 (right child of root)
t.get(t.parent(5)) // → 3 (parent of index 5)
t.height() // → 34. When to use
| Scenario | Why array |
|---|---|
| Binary heap | Complete tree, O(1) parent/child |
| Segment tree | Fixed-size complete tree |
| Priority queue | Heap array backing |
| Memory efficiency | No pointer overhead |
Summary
1-indexed arrays map cleanly to complete binary trees — O(1) navigation via parent, left, right formulas.
Next reads: Binary Search Trees · Binary Trees
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime