4.2.3 Representations: linked nodes vs array indexing (both 0-based and 1-based formulas) · GATE 2027 Programming and Data Structures

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

A binary tree has 12 leaves. How many nodes with two children? from Lesson 4.2.2
How many edges does a tree with n nodes have? from Lesson 4.1
How is a self-referential structure declared? from Lesson 1.6

1 · The Hook

🎣

A family tree can be kept as cards with arrows to each child, or as a numbered list where the children of person i are always persons 2i and 2i + 1. The first way handles any shape; the second needs no arrows at all, but only works well for trees without holes.

2 · Predict First

🤔

Store a complete binary tree in an array, level by level from index 0. Where are the children of the node at index 4? Its parent? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Children at 9 and 10 (2i + 1, 2i + 2); parent at 1 (⌊(i − 1)/2⌋).

Linked representation

Each node is a struct with the data and two pointers:

struct tnode {
    int data;
    struct tnode *left, *right;
};

struct tnode *mk(int x, struct tnode *l, struct tnode *r)
{
    struct tnode *t = malloc(sizeof(struct tnode));
    t->data = x;
    t->left = l;
    t->right = r;
    return t;
}

An empty subtree is NULL. The helper mk(x, l, r) builds a node with given subtrees, so a whole tree can be written as one nested expression:

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    printf("%d %d %d %d\n", root->data, root->left->right->data,
           root->left->right->left->data, root->right->right->data);
    return 0;
}

Output

1 5 7 6

Space: two pointers per node (n + 1 of them NULL). Works for any shape. Later programs in these notes use these helpers without repeating them.

Array representation, 0-based

Number the positions level by level, left to right, starting at 0. For the node at index i:

	0-based (root at 0)	1-based (root at 1)
left child	2i + 1	2i
right child	2i + 2	2i + 1
parent	⌊(i − 1)/2⌋	⌊i/2⌋
is i a valid node?	i < n (complete tree)	i ≤ n (complete tree)

No pointers are stored; the formulas replace them.

When the array wastes space

For a complete tree the n nodes fill indices 0 … n − 1 with no holes. Other shapes leave empty slots: a tree of height h may need up to 2^h+1^ − 1 slots. A right-skewed tree of n nodes needs 2^n^ − 1 slots for n values.

The example tree of this phase (1 at the root, 2 and 3 below, …) stored this way, with – for empty slots:

1  2  3  4  5  –  6  –  –  7

Which to choose

	Linked	Array
any shape	yes	wastes space unless complete
memory per node	data + 2 pointers	data only
find parent	not stored (add a pointer)	O(1) formula
insert anywhere	O(1) once found	may need resizing
typical use	search trees (Lesson 4.5)	heaps (Phase 5)

4 · Visual

Diagram: 4 · 3 · 2 · 1 · 7 · 9 · 5 · 4 · 1 · 0 · 3 · 2 · 6 · 6

The phase’s example tree with each node’s 0-based array index (small number). Node 7 sits at index 9 even though the tree has only 7 nodes: the array needs 10 slots.

Diagram: 1 · [0] · 2 · [1] · 3 · [2] · 4 · [3] · 5 · [4] · – · [5] · 6 · [6] · – · [7] · – · [8] · 7 · [9]

Array form (0-based). Empty slots (–) are wasted space.

1-based indexing of a complete tree with 6 nodes:

            [1]
          /     \
       [2]       [3]
       / \       /
    [4]   [5]  [6]

 children of i: 2i, 2i+1      parent of i: floor(i/2)
 node 3: children 6, 7 (7 > n, so only 6)   parent of 5: 2

1-based indices make the formulas shortest.

5 · Worked Examples

Example 1 Easy

In a 1-based array tree, where are the children and the parent of index 5?

Solution

Children 10 and 11; parent 2.

Example 2 Medium

A complete binary tree with 13 nodes is stored 0-based. Which indices hold leaves?

Solution

A node at i has a left child iff 2i + 1 ≤ 12, i.e. i ≤ 5. So indices 6 … 12 are leaves (7 leaves; check: n₂ = 6, n₁ = 0, n₀ = 7 = n₂ + 1).

Example 3 GATE

A binary tree of height 4 (edges) is stored in an array using 0-based level indexing. How many array slots must be reserved in the worst case? What if it is a complete tree with 20 nodes?

Solution

Worst case: all positions of a perfect tree of height 4: 2⁵ − 1 = 31 slots. A complete tree with 20 nodes uses exactly 20 slots (indices 0–19).

6 · GATE Traps

⚠️

0-based: children 2i + 1 and 2i + 2, parent ⌊(i − 1)/2⌋; 1-based: 2i, 2i + 1, parent ⌊i/2⌋. Do not mix them.
Array storage is compact only for complete trees.
A skewed tree with n nodes needs up to 2ⁿ − 1 array slots.
In the linked form, n + 1 child pointers are NULL.
The linked form has no parent pointer unless you add one.

8 · Memory Hook

🧠

“Double it to go down, halve it to go up.” In 1-based arrays children are 2i and 2i + 1 and the parent is i / 2.

9 · Connect the Dots

With a binary tree stored, the most basic task is visiting every node exactly once. Lists had one natural order; trees have several. Next lesson answers: in which orders can a binary tree be visited recursively, and what does each order produce?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markIndexing

In a 0-based array representation, the parent of index 9 is at:

(A) 5
(B) 8
(C) 4
(D) 3

Q2NAT1 markIndexing

In a 1-based array representation, what is the index of the right child of node 7?

Numerical answer: ________

Q3MCQ2 marksOutput

What does this print?

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    printf("%d %d %d %d\n", root->data, root->left->right->data,
           root->left->right->left->data, root->right->right->data);
    return 0;
}

(A) 1 5 4 3
(B) 1 4 7 6
(C) 1 5 7 6
(D) 1 2 4 6

Q4NAT2 marksSpace

A right-skewed binary tree with 5 nodes is stored with 0-based level indexing. What is the largest index used?

Numerical answer: ________

Q5MSQ1 markRepresentations

Which are true?

(A) The array form finds a parent in O(1).
(B) The array form needs pointers to children.
(C) A complete tree with n nodes fills array indices 0 … n − 1.
(D) The linked form stores n + 1 NULL pointers.

11 · Rule Card

Linked: struct tnode { data; *left; *right; }; empty subtree = NULL.
0-based: children 2i+1, 2i+2; parent ⌊(i−1)/2⌋.
1-based: children 2i, 2i+1; parent ⌊i/2⌋.
Array form compact only for complete trees; height h may need 2ʰ⁺¹ − 1 slots.
Heaps use arrays; search trees use links.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

linked representation (struct tnode)array representation0-based child/parent formulas1-based child/parent formulas

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

n − 1.
A struct containing a pointer to its own type, e.g. struct node { int data; struct node *next; };