Official PYQ · 2006Q13TreesMCQ1 mark

GATE CS 2006 Q13 — Trees

A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$ . the root is stored at $X[1]$ . For a node stored at $X[i]$ , the left child, if any, is stored in $X[2i]$ and the right child, if any, in $X[2i+1]$ . To be able to store any binary tree on n vertices the minimum size of $X$ should be

View worked solution

Answer: D

To store any arbitrary binary tree of $n$ vertices in the given array representation, we must size the array to accommodate the worst-case tree structure—the one that reaches the maximum possible index.

The maximum index is reached when the binary tree is completely right-skewed (i.e., every node has only a right child):

The root is at index $i_1 = 1$ .
The right child of the root is at index $i_2 = 2(1) + 1 = 3$ .
The right child of that node is at index $i_3 = 2(3) + 1 = 7$ .

In general, the index $i_k$ of the $k$ -th node in a right-skewed path satisfies the recurrence relation:

i_k = 2 \cdot i_{k-1} + 1 \quad \text{with} \quad i_1 = 1

Solving this recurrence:

\begin{aligned} i_1 &= 2^1 - 1 = 1 \\ i_2 &= 2^2 - 1 = 3 \\ i_3 &= 2^3 - 1 = 7 \\ &\ \ \vdots \\ i_n &= 2^n - 1 \end{aligned}

Thus, for a right-skewed binary tree with $n$ vertices, the last node is stored at index $2^n - 1$ . To ensure we can store any such tree, the minimum size of the array $X$ must be at least $2^n - 1$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

More Trees questions

GATE CS 2006 Q13 — Trees

Related questions