Question

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.

Answer 1

The array size needed for a binary tree not complete depends on the structure and depth. An extra two levels require an array of size 4N+3, a depth of 2 log N results in a size of N^2, and in the worst case, a degenerate tree needs a size of 2^N - 1.

Step-by-step explanation:

To determine how large an array needs to be to represent a binary tree which is not complete, we must consider each scenario that the question describes:

• A binary tree with two extra levels means essentially two additional full levels beyond a complete binary tree of N elements. If N is the last complete level, two more levels would be 2^(height+1) + 2^(height+2) - 1, where height is log2(N). This gives us a maximum array size of 4N+3
• For a binary tree with a deepest node at depth 2 log N, the worst-case size of the array would be 2^(2 log N + 1) - 1, which simplifies to approximately N^2.
• A binary tree with a deepest node at depth 4.1 log N would require an array size of 2^(4.1 log N + 1) - 1. This translates into a much larger array size that grows exponentially with N.
• The worst-case binary tree, which is a degenerate (or 'pathological') tree where each parent has only one child, would have N as its height, and the array size would need to be 2^N - 1 to accommodate all the elements, assuming the array starts at index 1.

In summary, the array size depends on the balance and structure of the binary tree. An extra level requires an array nearly four times the size of N, while a tree that is unbalanced to the extreme can require an array of size exponentially larger than N.

Answer 2

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)

Step-by-step 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)