Exam-style question
Try this first
Explain why the time complexity of binary tree search is O(log n). In your answer, describe what happens to the search after each comparison and relate this to the number of levels that may need to be examined.
Model answer
What a good answer should say
- Binary tree search compares the target with the current node and then follows only one of the two branches.
- The other branch is not examined for that search.
- Each comparison therefore reduces the remaining part of the tree that must be considered.
- As the number of values increases, the number of levels grows logarithmically rather than increasing by one level for every value.
Explanation
Why this works
The essential points are that a comparison selects one branch, the search does not examine both branches at every step, and the resulting number of levels is logarithmic in the number of values. These points justify O(log n).
Common mistake
No common mistake is linked to this question yet.