Tree representation

A logical tree can be stored in memory in several ways. The two most common for coursework and interviews are contiguous arrays (with index arithmetic) and pointer-based linked structures. This page compares them and shows small examples before the dedicated binary-tree lessons.

1) Array representation

Store nodes level by level (breadth-first order) in an array—usually 0-based in C. This works cleanly for complete binary trees and heaps; sparse or skewed trees waste slots.

Index formulas (0-based root at index 0)

If the child index is ≥ n (array length), that child is NULL / missing.

Example: complete binary tree in an array

Tree shape and values:

        10
      /    \
     20     30
    /  \    /
   40  50  60

Level order fills the array:

Index:  0   1   2   3   4   5
Value: 10  20  30  40  50  60

Check: parent of index 4 is (4-1)/2 = 1 (value 20); left child of index 1 is 2*1+1 = 3 (value 40).

Trade-offs (arrays)

• Pros: No pointer overhead; cache-friendly; fast parent/child via arithmetic (heaps).
• Cons: Wasted space for incomplete trees; insert/delete in the middle may require shifting or rebuilding—often awkward for arbitrary BSTs.

2) Linked representation

Each node is a struct allocated (e.g. with malloc) and points to its children. For a binary tree, two child pointers suffice.

Binary tree node (typical C)

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};
/* Missing child = NULL */

The same logical tree as above can be built by linking nodes: root’s left → node 20, right → 30, and so on. Traversals follow pointers—no index math.

Example: three-node linked tree

  root → [10]
          /    \
   [20]         [30]
 left,right   left,right
 (to NULL     (often NULL
  or subtree)  for leaves)

N-ary trees (brief)

When a node may have many children, common options are: (1) an array or list of child pointers, or (2) first child + next sibling within a binary-shaped “representation tree”:

struct Node {
    int data;
    struct Node *first_child;
    struct Node *next_sibling;
};
/* Converts an N-ary tree to a binary-tree-shaped overlay */

3) Array vs linked (summary)