The average depth of a binary search tree is:
2011
The average depth of a binary search tree is:
- A.
O(n0.5)
- B.
O(n)
- C.
O(log n)
- D.
O(n log n)
Attempted by 375 students.
Show answer & explanation
Correct answer: C
For a randomly constructed binary search tree with n nodes, the expected average depth is O(log n). While the worst-case depth can be O(n) for a skewed tree, standard analysis assumes random insertion order, leading to logarithmic average depth.
A video solution is available for this question — log in and enroll to watch it.