Estimate expected comparisons in a BST
OptiverSoftware Engineer · Online Assessment
Last updated
Estimate expected comparisons in a BST evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.