Binary Search tree: What are the correct answers to the question below: A comple

Question

Binary Search tree: What are the correct answers to the question below:

A complete binary tree is stored in an array called treeNodes. which is indexed from 0 to 99. as described in Section 8.9. The tree contains 85 elements. Mark each of the following statements as true or false, and explain your answers. a. treeNodes [42] is a leaf node. b. treeNodes [41] has only one child. C. The right child of treeNodes [12] is treeNodes [25]. d. The subtree rooted at treeNodes [7] is a full binary tree with four levels. e. The tree has seven levels that are full, and one additional level that contains some elements.

Explanation / Answer

Total size of Nodes = 85

So first leaf node will be at index: n/2 = 85/2 = 42

A. true

b. false => each node has either 2 or 0 child

c. false => Right child of 12 => 2*12 + 2 = 26

d. false=>

2^(h+1) - 1 = 85

2^(h+1) = 86
h + 1 = log2(85)
h+1 = 6.4
h = 5.4
h = ceil(5.4) = 6

or
The level of a complete, balanced tree of index2.gif nodes is log(n+1)
log(85+1) => 6.4 = 6

e. false

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.