Binary Tree Representations

There are two main ways to represent a binary tree:

Method	Description
1. Array Representation	Tree is stored as an array (indexing rules are used).
2. Linked Representation	Each node has pointers to its left and right child.

1. 📦 Array Representation of Binary Tree

In this method:

• The tree is stored in a one-dimensional array.

• Each node's position depends on the index of its parent.

✅ Index Rules:

If a node is stored at index i:

• Left Child → stored at index 2i + 1

• Right Child → stored at index 2i + 2

• Parent → stored at index (i - 1)/2 (integer division)

---

✏️ Example

Let's consider this binary tree:

        A
      /   \
     B     C
    / \   /
   D   E F

Store in array (level order):

Index	0	1	2	3	4	5
Value	A	B	C	D	E	F

Thus:

• A at index 0

• B at index 1 → left child of A

• C at index 2 → right child of A

• D at index 3 → left child of B

• E at index 4 → right child of B

• F at index 5 → left child of C

---

✅ Advantages of Array Representation

• Easy and fast access (just index calculations).

• Best suited for complete binary trees (like heaps).

❌ Disadvantages

• Wastes space for non-complete trees (many NULLs).

• Difficult to manage dynamic insertion/deletion.

Example:

Construct a binary tree from the following elements arranged in an array A[1:15] as:
1    2    3  4  5  6  7  8  9  10  11  12  13  14  15
A   B   C  D     E          F              G   H

C Program Array Representation of Tree

#include <stdio.h>

#define MAX 100

int tree[MAX];

// Initialize tree

void init() {

    for (int i = 0; i < MAX; i++)

        tree[i] = -1; // -1 indicates empty

}

// Insert into tree

void insert(int data, int index) {

    if (tree[index] != -1) {

        printf("Node already occupied\n");

    } else {

        tree[index] = data;

    }

}

int main() {

    init();

    insert(1, 0); // Root node

    insert(2, 1); // Left child of root

    insert(3, 2); // Right child of root

    insert(4, 3); // Left child of node at index 1

    printf("Root: %d\n", tree[0]);

    printf("Left Child of Root: %d\n", tree[1]);

    printf("Right Child of Root: %d\n", tree[2]);

    return 0;

}

2. 🔗 Linked Representation of Binary Tree

Here:

• Each node is a structure (or object) with 3 parts:

  • Data

  • Pointer to Left Child

  • Pointer to Right Child

---

✏️ Structure

In C language:

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

Each node is dynamically created and linked.

✅ Advantages of Linked Representation

• Memory efficient for sparse trees.

• Easy to perform dynamic insertion and deletion.

❌ Disadvantages

• Slower random access (must traverse pointers).

• Requires more memory (extra space for pointers).

C Program Linked Representation of Binary Tree

#include <stdio.h>

#include <stdlib.h>

// Define the structure

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

};

// 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;

}

// Simple Main

int main() {

    struct Node* root = createNode(1);

    root->left = createNode(2);

    root->right = createNode(3);

    root->left->left = createNode(4);

    root->left->right = createNode(5);

    printf("Root Node: %d\n", root->data);

    printf("Left Child of Root: %d\n", root->left->data);

    printf("Right Child of Root: %d\n", root->right->data);

    return 0;

}