Estimate expected comparisons in a BST
Overview
This question evaluates understanding of binary search tree structure, average-case search cost, and basic probability (expected value) within algorithm analysis, and it belongs to the Coding & Algorithms domain focusing on data structures and performance analysis.
Optiver
Jul 17, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
In a particular binary search tree, finding node A takes 1 comparison and finding node D takes 3 comparisons. What is the expected number of comparisons to find a uniformly random node in this tree? State assumptions and justify your estimate.