What is the time taken for a range query for a perfectly balanced tree?

Category: QuestionsWhat is the time taken for a range query for a perfectly balanced tree?
Editor">Editor Staff asked 1 month ago

What is the time taken for a range query for a perfectly balanced tree?
 
(a) O(N)
 
(b) O(log N)
 
(c) O(√N+M)
 
(d) O(√N)
 
I want to ask this question from Trees topic in division Trees of Data Structures & Algorithms I
 
I got this question in an interview.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct answer is (c) O(√N+M)
 
Easy explanation – For a perfectly balanced k-d tree, the range query could take O(√N+M) in the worst case to report M matches.