Problems 7) e and f In java language PART I 7) Given the following list of valuc

Question

Problems 7) e and f
In java language PART I 7) Given the following list of valucs: 45, 54, 89, 32, 23, 58, 65, 76, 88, 55, 42, 12, 38, 34, 57, 79, 90, 66 a) Draw the binary search tree that would evolve by inserting the values into the tree in the order in which they are presented b) Draw the array representation of this binary search tree. You may use .. notation as long as you label the array cells c) In what order would you insert the values so as to get a complete binary search tree? d) In what order would you insert the values so as to get a linked list that uses left references only? Right references only? e) How many elements would be needed for each of the binary trees described in part d if implemented as arrays? D Why are binary search tree more often implemented using linked structures rather than arrays?

Explanation / Answer

Solution:

7)

e)

There are 18 elements in the array and if we are building a tree which is either left skewed or right skewed then the maximum height of the tree will be O(n)

which means 18 nodes.

and we no that with the height n a binary tree contains 2^n - 1 nodes.

which means here,

2^18 - 1 = 262143 elements would be required.

f)

Since the array is a continuous memory allocation data structure which means if the tree is not completely balanced or with the optimal height the memory wastage would be there, like in the above example 262143 elements are required.

A linked list can do it in 18 nodes.

which means space saving.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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