An array X of n distinct integers is interpreted as a complete binary tree.…
2006
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is
- A.
⌊log2 i⌋
- B.
⌈log2 (i + 1)⌉
- C.
⌊log2 (i + 1)⌋
- D.
⌈log2 i⌉
Attempted by 325 students.
Show answer & explanation
Correct answer: C
Answer: The level of X[i] is ⌊log₂ (i + 1)⌋.
Reasoning:
Nodes at level L in a complete binary tree occupy indices from 2^L - 1 through 2^{L+1} - 2 (0-based indexing).
Add 1 to each part of the inequality: i + 1 ranges from 2^L to 2^{L+1} - 1.
Taking base-2 logarithms gives L ≤ log₂(i + 1) < L + 1, so L = ⌊log₂ (i + 1)⌋.
Quick examples:
i = 1: ⌊log₂(2)⌋ = 1 (level 1).
i = 2: ⌊log₂(3)⌋ = 1 (level 1).
i = 3: ⌊log₂(4)⌋ = 2 (level 2).