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)