Data structures and algorithms
A balanced binary search tree holds one million keys.
FoundationNumeric answer
A balanced binary search tree holds one million keys. How many comparisons does a lookup need in the worst case?
Answer with a number. Fractions, powers and expressions like 23/6 or C(52,5) are read correctly in practice.
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
Report an issue with this question
Learn the method
Of the kind reported at
Optiver, Citadel Securities, Hudson River Trading, Jump Trading
More data structures and algorithms questions
- You need prefix sums with point updates on a large array. Fenwick tree or segment tree?Advanced · Premium
- What is the height (edges on the longest root-to-leaf path) of a binary heap…Foundation · Premium
- How many structurally different binary search trees can hold the keys 1,2,3,4,5?Applied · Premium
- You need the 100 largest values from a stream of 10⁹ numbers you cannot store.Foundation · Free solution
- What does the recurrence T(n) = 2T(n/2)+O(n) solve to?Applied · Free solution
- What is the running time of Dijkstra’s algorithm with a binary heap, on a graph…Applied · Premium