Exam-style question
Try this first
A binary tree search examines one node at the root and then follows one of the two branches. What is the main reason this produces logarithmic time complexity?.
- A.The search examines every node in the tree
- B.The search removes one node from consideration at each step
- C.The search follows one branch, reducing the remaining search area at each step
- D.The search sorts all nodes before examining them
Model answer
What a good answer should say
- C.
- The search follows one branch, reducing the remaining search area at each step
Explanation
Why this works
At each comparison, the search chooses one branch rather than continuing through both parts of the tree. This repeated reduction gives the required O(log n) time complexity.
Common mistake
No common mistake is linked to this question yet.