The average depth of a binary search tree is:

2011

Answer: C. O(log n) — 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,…

A.
O(n0.5)
B.
O(n)
C.
O(log n)
D.
O(n log n)

Attempted by 1102 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2