Question: Suppose you are given a Binary Tree ( that is NOT a Binary Search Tree...so items are NOT sorted in any order in the tree

Suppose you are given a Binary Tree (that is NOT a Binary Search Tree...so items are NOT sorted in any order in the tree). Also suppose that you are trying to implement the find() method on this data structure (find whether or not a given element is in the tree). Which of the following statements is MOST true about the worst-case runtime of this method.
A) It is still possible to implement the find() method in worst-case (log(n)) time.
B) The find() method cannot be written to guarantee (log(n)) time, but it can be written such that it often is, and only occasionally runs slower than (log(n)) time.
C) The find() will be (n). It might terminate early if we find the element, but the worst-case will always be that we examine every element in the tree.
D) The find() method can be written such that it takes worst-case linear time, (n), but it will ALWAYS terminate before examining every element of the tree.
E) The find() method will have a runtime that is strictly worse than linear time, (n).
Suppose you are given a Binary Tree ( that is NOT

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Accounting Questions!