-
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
-
- log2 n
- n
- 2n + 1
- 2n – 1
- log2 n
Correct Option: D
For a right skewed binary tree, number of nodes will be 2^ (n – 1). For example, in below binary tree, node 'A' will be stored at index 1, 'B' at index 3, 'C' at index 7 and 'D' at index 15.
