Binary Tree Representation in Data Structures

 Binary Tree Representation in Data Structures

A Binary Tree can be represented in different ways in memory. The two most common representations are:

---

📌 1. Using Linked Representation (Pointer-Based)

In this method, each node is represented as a structure (or class) containing:
✔ Data – The actual value stored in the node.
✔ Left Pointer – A reference to the left child.
✔ Right Pointer – A reference to the right child.

Example (C-like Representation):

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

💡 Advantages:
✅ Dynamic memory allocation, so space is used efficiently.
✅ Flexible, allowing easy insertion and deletion of nodes.
❌ Slightly more memory required due to pointers.

---

📌 2. Using Array Representation (Sequential Representation)

A Binary Tree can also be stored in an array, especially for Complete Binary Trees.

🔹 Indexing Rules for Array Representation:

• Root node is stored at index 0.
• Left child of node at index i → Stored at index 2*i + 1.
• Right child of node at index i → Stored at index 2*i + 2.
• Parent of node at index i → Stored at index (i-1)/2.

Example (Array Representation of a Binary Tree):

Tree Structure:

        10
       /  \
      20   30
     /  \
    40   50

Array Representation:

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

💡 Advantages:
✅ Requires less memory (no need for pointers).
✅ Faster indexing (O(1) access using index calculations).
❌ Not efficient for unbalanced trees (wastes memory for null children).

---

📌 Which Representation to Use?

✔ Use Linked Representation when dealing with dynamic trees (e.g., BSTs).
✔ Use Array Representation when dealing with Complete Binary Trees or Heaps.