Array Representation of Binary Trees

 

Array Representation of Binary Trees 🌳

In Array Representation, a Binary Tree is stored in a sequential manner using an array. This method is most efficient for Complete Binary Trees but can lead to memory wastage in Sparse Trees (trees with missing nodes).

---

📌 Indexing Rules for Array Representation

For a node at index i in an array:
🔹 Parent Node → Stored at index (i - 1) / 2
🔹 Left Child → Stored at index 2 * i + 1
🔹 Right Child → Stored at index 2 * i + 2

---

📌 Example of Array Representation

Tree Structure:

markdown
        10
       /  \
      20   30
     /  \
    40   50

Array Representation:

makefile
Index:  0   1   2   3   4  
Value: [10, 20, 30, 40, 50]

✅ Index Mapping:

• Root (10) → arr[0]
• Left Child of 10 (20) → arr[1] = arr[2*0 + 1]
• Right Child of 10 (30) → arr[2] = arr[2*0 + 2]
• Left Child of 20 (40) → arr[3] = arr[2*1 + 1]
• Right Child of 20 (50) → arr[4] = arr[2*1 + 2]

---

📌 Advantages of Array Representation:

✅ Less memory overhead (no need for pointers).
✅ Fast access using index calculations (O(1) lookup).
✅ Works well for complete & full binary trees.

📌 Disadvantages of Array Representation:

❌ Wastes space for sparse trees (missing nodes still take up space).
❌ Insertion & deletion are expensive (requires shifting elements).

---

📌 When to Use Array Representation?

✔ Efficient for Complete Binary Trees & Heaps (used in Priority Queues).
✔ Not ideal for unbalanced or sparse trees (better to use linked representation).