Array Implementation of Binary Trees

Array Implementation of Binary Trees – Complete DSA Guide

(Concept • Index Formula • Example • Code • Pros & Cons)

A Binary Tree can be implemented using an array instead of pointers.
This method is simple and efficient for certain types of binary trees.

1️⃣ What is Array Implementation of Binary Tree?

In array implementation, tree nodes are stored in an array in a level-wise (level order) manner.

Instead of using pointers (left, right), we use index calculations.

2️⃣ Index Formula (Very Important)

If a node is stored at index i:

Relation	Formula
Left Child	`2*i + 1`
Right Child	`2*i + 2`
Parent	`(i - 1) / 2`

Root node is always at index 0

3️⃣ Example Binary Tree

Tree Structure

Array Representation

4️⃣ How Mapping Works

Root A → index 0
Left of A → 2*0+1 = 1 → B
Right of A → 2*0+2 = 2 → C
Left of B → 2*1+1 = 3 → D
Right of B → 2*1+2 = 4 → E

5️⃣ Array Implementation Example (C++)

#include <iostream>
using namespace std;int main() {
char tree[10];tree[0] = 'A';
tree[1] = 'B';
tree[2] = 'C';
tree[3] = 'D';
tree[4] = 'E';
tree[5] = 'F';

cout << "Root: " << tree[0] << endl;
cout << "Left child of root: " << tree[1] << endl;
cout << "Right child of root: " << tree[2] << endl;

return 0;
}

#include <iostream>

using namespace std;int main() {

char tree[10];tree[0] = 'A';

tree[1] = 'B';

tree[2] = 'C';

tree[3] = 'D';

tree[4] = 'E';

tree[5] = 'F';

cout << "Root: " << tree[0] << endl;

cout << "Left child of root: " << tree[1] << endl;

cout << "Right child of root: " << tree[2] << endl;

return 0;

}

Output

6️⃣ Traversal Using Array Representation

In-order Traversal (Recursive Logic Using Index)

7️⃣ When Array Implementation is Best

✔ Complete Binary Trees
✔ Heaps (Min Heap / Max Heap)
✔ Binary Trees with fixed structure

📌 This is why Heap is always implemented using arrays.

8️⃣ Limitations of Array Implementation

❌ Wastes memory for sparse trees
❌ Not suitable for skewed trees
❌ Fixed size
❌ Difficult insertion/deletion

9️⃣ Array vs Linked Representation

Feature	Array Representation	Linked Representation
Memory	Contiguous	Non-contiguous
Best for	Complete Trees	Any Tree
Space Wastage	High (sparse trees)	Low
Flexibility	Low	High

🔟 Real-Life & DSA Uses

✔ Heap data structure
✔ Priority Queue
✔ Tournament trees
✔ Implicit tree representation

Interview Questions (Very Common)

Q1. Why heaps use array implementation?
👉 Because heap is a complete binary tree

Q2. Formula for left & right child?
👉 2*i+1, 2*i+2

Q3. When array representation is not suitable?
👉 Sparse or skewed trees

Final Summary

✔ Binary tree can be implemented using array
✔ Root at index 0
✔ Simple index formulas replace pointers
✔ Best for complete binary trees
✔ Poor choice for sparse trees

Array Implementation of Binary Trees