Question 2 of 8: Tree Implementation

Question 2: Tree Implementation (10 marks: 4, 4, 2)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Approach. The array stores the tree level-by-level, left-to-right (a "complete tree" layout), so a node's relatives are pure arithmetic on its index — no pointers are stored or followed.

1. Parent index — 4 marks

For 0-indexed storage, node n's parent is at index $\left\lfloor \dfrac{n-1}{2} \right\rfloor$, and the root (n = 0) has no parent.

int parent(int* data, int n, int* out) {
    if (n <= 0) return 0;              /* root has no parent */
    *out = data[(n - 1) / 2];          /* integer division truncates */
    return 1;
}

2. Right-child index — 4 marks

Node n's right child is at index $2n + 2$; it exists only if that index is still within the stored range [0, size).

int right_child(int* data, int n, int size, int* out) {
    int idx = 2 * n + 2;
    if (idx >= size) return 0;         /* no right child stored */
    *out = data[idx];
    return 1;
}

3. Internal (non-leaf) node count — 2 marks

A node is internal exactly when its left child index, $2i+1$, still lies inside the array — i.e. indices $0, 1, \dots, \lfloor n/2 \rfloor - 1$ are internal and the rest are leaves: $$\text{internal nodes} = \left\lfloor \frac{n}{2} \right\rfloor, \qquad \text{leaves} = n - \left\lfloor \frac{n}{2} \right\rfloor = \left\lceil \frac{n}{2} \right\rceil.$$