+1 vote
688 views

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)$
asked in DS | 688 views
Option C
is it same as hight of bst
and worst case of Binary Search Tree is O(n).  #extraInfo

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

option C

selected by

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)