717 views
2 votes
2 votes
a binary search tree with n elements are constructed by randomly taking the elements one by one. What is the expected height of the tree

3 Answers

1 votes
1 votes
Worst case O(n): if final outcome is SKEWED TREE

Average case (log n ): if balanced.

So expected hight will be between    log n  and   n

Related questions

1 votes
1 votes
0 answers
1
Rohit Gupta 8 asked Dec 25, 2017
1,110 views
If the average depth of a node in an $n$-node binary search tree is $O(\log{n})$, then the height of the tree is$O(n\log{n})$$O(n)$$O(\log{n})$$O(\sqrt(n\log{n}))$
0 votes
0 votes
2 answers
2
dhruba asked Jun 5, 2023
1,094 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...