Pointer (Linked List) Representation of Binary Trees

 

Pointer (Linked List) Representation of Binary Trees 

In the pointer-based (linked list) representation, each node of the binary tree is represented as a structure (or class) containing:
✔ Data – The actual value stored in the node.
✔ Pointer to Left Child – Points to the left subtree.
✔ Pointer to Right Child – Points to the right subtree.

This representation is dynamic and memory-efficient, making it ideal for trees that grow and shrink frequently.

---

📌 Structure of a Node (C/C++ Example)

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

💡 Each node stores the data and has two pointers to its left and right children.

---

📌 Example Binary Tree Representation

Tree Structure:

        10
       /  \
      20   30
     /  \
    40   50

Linked Representation (Memory Pointers):

 Node(10)
  /      \
(20)    (30)
 /  \
(40) (50)

---

📌 Code Implementation in C

#include <stdio.h>
#include <stdlib.h>

// Define a Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to print the tree in Inorder Traversal
void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    // Creating nodes
    struct Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);
    root->left->left = createNode(40);
    root->left->right = createNode(50);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    return 0;
}

🔹 Output:

Inorder Traversal: 40 20 50 10 30

---

📌 Advantages of Pointer Representation

✅ Dynamic Memory Allocation – Efficiently handles tree modifications.
✅ No Wasted Space – Unlike arrays, only necessary nodes are allocated memory.
✅ Easy Insertion & Deletion – No need to shift elements like in arrays.

📌 Disadvantages

❌ Extra Memory for Pointers – Each node requires additional space for two pointers.
❌ Slower Random Access – Traversing the tree requires pointer dereferencing.

---

📌 When to Use Linked Representation?

✔ Best for Dynamic Trees – Useful when tree size changes frequently.
✔ Ideal for BST, AVL Trees, and Huffman Trees – Operations like insertion/deletion are efficient.

🌲 Pointer representation is widely used in practical applications like expression trees, decision trees, and database indexing