A scheme for storing binary trees in an array X is as follows. Indexing of X…
2006
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.
- A.
log2n
- B.
n
- C.
2n + 1
- D.
2n - 1
Attempted by 179 students.
Show answer & explanation
Correct answer: D
Key idea: consider the worst-case (a completely skewed tree) where each node has only one child.
With the given indexing, the root is at index 1; a right child of a node at index i is at index 2i + 1.
For a path where every node is the right child, the indices are 1, 3, 7, 15, … which follow the formula 2^d - 1 for a node at depth d.
If the tree has n nodes in this worst case, the deepest node is at depth n and occupies index 2^n - 1.
Therefore the array must have size at least 2^n - 1 to be able to store any binary tree on n vertices.
Answer: 2^n - 1
A video solution is available for this question — log in and enroll to watch it.