GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
1.2k 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 by Veteran (79k points)   | 1.2k views
Option C
is it same as hight of bst
and worst case of Binary Search Tree is O(n).  #extraInfo

2 Answers

+5 votes
Best answer

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

option C

answered by Loyal (3.3k points)  
selected by
+3 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) 

answered by Loyal (4k points)  


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4138 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,214 comments
30,083 users