Tree Representation - PCCST303

A tree exists conceptually as nodes and connections, but it has to be stored in memory somehow. There are two standard ways: linked representation, using pointers, and array representation, using index arithmetic.

Linked representation

Definition

In the linked representation, each node is a structure with a data field and one pointer per possible child. For a binary tree, that's a LEFT pointer and a RIGHT pointer.

In C:

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

For a leaf node, both left and right are NULL, exactly the way the last node's next is NULL in a linked list. Nodes are allocated one at a time as the tree grows, so a linked tree costs no more memory than the nodes actually in use.

Array representation

Definition

In the array representation, tree nodes are stored in a single flat array, and the parent-child relationship is captured by index arithmetic rather than pointers.

For a complete binary tree stored in a zero-indexed array, a node at index i has:

left child  = 2i + 1
right child = 2i + 2
parent      = (i - 1) / 2      (integer division)

Consider this complete binary tree:

Stored level by level, left to right:

Index

0123456

For B at index 1:

left  = 2(1) + 1 = 3 → D
right = 2(1) + 2 = 4 → E
parent = (1 - 1) / 2 = 0 → A

These formulas only work correctly if the tree is complete: every level is full except possibly the last, and the last level fills in from the left with no gaps. (Completeness is covered in full in Binary Tree Types and Properties; for now it's enough to know a complete tree has no missing node anywhere except at the end of the last level.)

Note

If the tree is not complete, this array layout either wastes slots on the missing children, or worse, silently makes the index formulas point to the wrong node.

Choosing the right representation

Feature	Linked	Array
Memory	Allocated as needed	Preallocated, fixed size
Finding a child	Follow a pointer	Compute an index
Sparse / unbalanced tree	Space-efficient	Can waste a lot of space
Complete tree	Works fine	Very space- and cache-efficient
Inserting/deleting a node	Relink a few pointers	May require shifting many elements to keep the array a valid complete tree
Typical use	General binary trees, BSTs	Binary heaps (always complete)

This is why binary heaps are almost always array-backed: a heap is required to stay a complete tree by definition, so the array formulas always apply cleanly, and there's no pointer-chasing overhead. A general binary search tree, on the other hand, is rarely complete, so it's normally linked instead.

Quick recall

Linked representation: each node stores LEFT and RIGHT pointers (NULL for a missing child); memory grows with the tree.
Array representation: node i has children at 2i+1 and 2i+2, and parent at (i-1)/2 (zero-indexed); only correct for complete trees.
Linked representation suits general and sparse trees; array representation suits complete trees, most notably binary heaps.