Ask 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.

+1
Answers (1)
  1. 1 December, 06:44
    0
    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)
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers