Estimate expected comparisons in a BST
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
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.
Quick Answer: 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.