ISRO CSE 2011 | Question: 62

Question

The average depth of a binary search tree is

• A. $O(n^{0.5})$
• B. $O(n)$
• C. $O(\log n)$
• D. $O(n \log n)$

Comments

Option C

---

is it same as hight of bst

---

and worst case of Binary Search Tree is O(n).  #extraInfo

Answer 1

The average case depth of a node in a BST is O(lg n)

option C

Answer 2

A binary search tree is a binary tree with the further property that, for every node,

 

the value of the element in the left child is less than the value of the element at the node, and

the value of the element in the right child is greater than the value of the element at the node

The average depth over all nodes in a binary search tree is O(lg n) 

Answer 3

In the worst case, a binary search tree is skewed. The depth of such a tree would be O(n).

The worst case would occur when the key values are added to the binary search tree in a sorted order.

 

But in the average case, the key sequence won't be sorted — it'd be a random mix, which gives us O(logn) depth in the average case. Option C.

---

---

Bonus:

Even in the worst case, the depth of balanced binary trees like AVL trees is O(logn).