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

+1 vote
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 Answer

+1 vote
by (789k points)
selected by

Best answer
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).

+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
0 votes
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+1 vote
1 answer
+2 votes
1 answer
+1 vote
1 answer