A complete binary tree of N elements uses array positions 1 to N. Suppose we try to use an array representation of a binary tree that is not complete. Determine how large the array (in terms of N) must be?

A. A binary tree that has two extra levels (that is, it is slightly unbalanced).

B. A binary tree that has a deepest node at depth 2 log N.

C. A binary tree that has a deepest node at depth 4.1 log N.

D. The worst-case binary tree.

The correct answer is (a) 4n (b) the array size must in O (N^2) (c) O (n^4.1) (d) In the worst case the binary tree formed will be a skew tree in that case to represent n elements the array must be O (2^n)

Explanation:

Given that:

(A) because it had two more levels, the array should have a size of 4n, the first level will have n nodes and the second level will have 2n nodes

Thus,

Total n+n+2n = 4n

(B) since the deepest node is at 2Log N = log N2

The height of complete binary tree with x nodes is log (x). Because the deepest node is at log N2 there must be N2 nodes. so the array size must in O (N^2).

(C) In the same as subpart of b, the answer is still O (n^4.1)

(D) For the worst case the binary tree formed will be a skew tree in that case to represent n elements the array must be O (2^n)