Representation of Binary Trees in Memory

🌲 A Quick Reminder: What’s a Binary Tree?

A binary tree looks something like this:

        [A]
       /   \
     [B]   [C]
    /   \
  [D]   [E]

Here:

• A is the root node (the top of the tree).
• B and C are children of A.
• D and E are children of B.

When we draw it, it looks easy to understand. But computers don’t have “branches” and “circles” — they only understand memory cells and pointers.
So we need a way to represent this structure in a way that the computer can handle efficiently.

There are two main ways to represent a binary tree in memory:

1. Array Representation
2. Linked Representation

Let’s explore both in a fun and easy way.

---

🧮 1. Array Representation

Imagine storing a tree in an array — just like keeping elements in a list where each position has a fixed index.

Here’s how it works:

• The root node is stored at index 1 (not 0, to make math easy).
• For any node stored at position i:
• The left child is stored at position 2 * i
• The right child is stored at position 2 * i + 1

Let’s see this in action.

🌿 Example Tree:

        [A]
       /   \
     [B]   [C]
    /   \
  [D]   [E]

🧠 Array Representation:

Index	Node
1	A
2	B
3	C
4	D
5	E

Now let’s apply the formula:

• Root A is at index 1
• Left child of A → 2 × 1 = 2 → B
• Right child of A → 2 × 1 + 1 = 3 → C
• Left child of B → 2 × 2 = 4 → D
• Right child of B → 2 × 2 + 1 = 5 → E

That’s how the positions are calculated!

✅ Pros:

• Simple and fast to access any node.
• Great for complete binary trees (where all levels are filled).

❌ Cons:

• Wastes memory when the tree is not full.
  (Because some indices in the array stay empty.)

---

🔗 2. Linked Representation

Now imagine building the tree using linked nodes, just like a linked list, but with two pointers instead of one.

Each node has three parts:

1. Data (the value stored in the node)
2. Left pointer (address of left child)
3. Right pointer (address of right child)

It’s like this:

 -------------------------
|  Data  | Left | Right  |
 -------------------------

Each pointer connects one node to another, forming the full binary tree structure.

🌿 Example:

Let’s take the same tree again:

        [A]
       /   \
     [B]   [C]
    /   \
  [D]   [E]

Now let’s imagine how it looks in memory:

   +------+---------+---------+
   |  A   |  B(ptr) |  C(ptr) |
   +------+---------+---------+
          /           \
   +------+---------+---------+
   |  B   |  D(ptr) |  E(ptr) |
   +------+---------+---------+
          /           \
   +------+---------+---------+
   |  D   |  NULL   |  NULL   |
   +------+---------+---------+
   +------+---------+---------+
   |  E   |  NULL   |  NULL   |
   +------+---------+---------+
   +------+---------+---------+
   |  C   |  NULL   |  NULL   |
   +------+---------+---------+

Here:

• Each “ptr” is a memory address pointing to another node.
• NULL means there’s no child in that direction.

So, the computer connects these pointers in memory to form the complete structure — just like connecting pieces of a puzzle.

---

✅ Pros:

• No wasted memory, even if the tree is incomplete.
• Easy to grow or shrink the tree dynamically.
• Suitable for all kinds of trees (not just complete ones).

❌ Cons:

• Takes extra space for storing pointers.
• Slightly slower to access elements than array representation.

---

🧾 Summary: Array vs Linked Representation

Feature	Array Representation	Linked Representation
Storage	Uses array indexes	Uses pointers
Best for	Complete binary trees	Any kind of binary tree
Memory use	May waste space	Efficient memory use
Ease of insertion/deletion	Hard	Easy
Access time	Fast (using index)	Slower (need to follow links)

---

🖼️ Simple Diagram: Two Ways to Store a Binary Tree

Binary Tree:
        [A]
       /   \
     [B]   [C]
    /   \
  [D]   [E]

-------------------------------
Array Representation:
Index:  1   2   3   4   5
Node : [A] [B] [C] [D] [E]
-------------------------------

Linked Representation:
[A]
 / \
[B] [C]
 / \
[D] [E]
(Each node has pointers: Left → Right)

---