Describe the most time-efficient way to implement the operations listed below an

Question

Describe the most time-efficient way to implement the operations listed below and give the order (Big O) in terms of N. Given a queue of N integers, find the minimum value in the queue and delete it from the queue. When you finish, the rest of the values must be in their original order. Given a binary search tree of N integers, find the median value and delete it. For this question, assume N is odd. [Note: If the values were in a sorted array, the median value would be at index (N -1)/2. For example, the median of {1, 4, 9,10, 17} is at (5 -1)/2 = 2 which is 9.]

Explanation / Answer

1) O(N), since finding a min value will take O(N) time. Once find, we need to remove it and change the places all elements above it by one (O(N)).

2) O(N) . The idea is that in-order traversal (O(N)) processes nodes in BST in sorted manner. So, since the tree is a BST, the ith node you process, is the ith node in order, this is of course also true for i==(n-1)/2, and when you find it is the (n-1)/2th node, you return it.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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