What is the expected depth of a node in a randomized binary search tree?

Category: QuestionsWhat is the expected depth of a node in a randomized binary search tree?
Editor">Editor Staff asked 1 month ago

What is the expected depth of a node in a randomized binary search tree?
 
(a) log n
 
(b) n!
 
(c) n^2
 
(d) 2 log n + O(1)
 
Asked question is from Binary Trees topic in section Binary Trees of Data Structures & Algorithms I
 
This question was posed to me in quiz.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct choice is (d) 2 log n + O(1)
 
For explanation: The expected value of depth of a node that is for a node a, the expected value of length of path from root to node a is found to be at most 2 log n + O(1).