retagged by
21,466 views
9 votes
9 votes

The average depth of a binary search tree is

  1. $O(n^{0.5})$
  2. $O(n)$
  3. $O(\log n)$
  4. $O(n \log n)$
retagged by

3 Answers

Best answer
9 votes
9 votes

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

option C

selected by
4 votes
4 votes

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) 

1 votes
1 votes

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

Answer:

Related questions

10 votes
10 votes
3 answers
1
ajit asked Oct 1, 2015
10,203 views
How many distinct binary search trees can be created out of $4$ distinct keys?$5$$14$$24$$35$
4 votes
4 votes
4 answers
2
Isha Gupta asked Jun 15, 2016
7,467 views
The in-order traversal of a tree resulted in FBGADCE. Then the pre-order traversal of that tree would result inFGBDECAABFGCDEBFGCDEAAFGBDEC
9 votes
9 votes
7 answers
3
shibu asked Jun 15, 2016
7,347 views
If node A has three siblings and B is parent of A, what is the degree of A?0345
8 votes
8 votes
1 answer
4
shivanisrivarshini asked May 31, 2016
11,384 views
Let $T(n)$ be defined by $T(1) =10$ and $T(n+1)=2n+T(n)$ for all integers $n \geq 1$. Which of the following represents the order of growth of $T(n)$ as a function of $n...