search
Log In
0 votes
211 views
8. What are the worst case and average case complexities of a binary search tree?
a) O(n), O(n)
b) O(logn), O(logn)
c) O(logn), O(n)
d) O(n), O(logn)
in Programming 211 views
0
For which operation? Searching?

1 Answer

1 vote
D: Worst case occurs when BST is skewed O(n);  Best case occurs when it is Height Balanced O(logn)   in case of insertion, search and delete operations
0
Yes answer would be d

Related questions

3 votes
3 answers
1
1.4k views
Suppose we do not have a parent pointer in the nodes of a search tree, only left-child and right-child. Which of the following operations can be computed in time $O(\log n)$ for a balanced search tree? 1- find, insert, delete, but not min, max, pred, succ 2- find, insert, ... not pred, succ 3- find, insert, delete, pred, succ but not min, max 4- All of find, insert, delete, min, max, pred, succ
asked Aug 23, 2016 in Algorithms dd 1.4k views
9 votes
1 answer
2
598 views
Q1. How many binary search trees possible with $11$ distinct key? Q2. How many binary search trees possible with $11$ un-labelled nodes? Q3. How many binary search trees possible with $11$ labelled nodes? Q4. How many binary trees possible with $11$ distinct key? Q5. How many binary trees possible with $11$ un-labelled nodes? Q6. How many binary trees possible with $11$ labelled nodes?
asked Feb 2, 2018 in DS Lakshman Patel RJIT 598 views
2 votes
4 answers
3
1.1k views
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?
asked Jan 16, 2019 in DS sripo 1.1k views
2 votes
1 answer
4
196 views
I have doubt when its asked to know number of labelled and unlabelled binary tree : For labelled = (On basis of labelling) T(n) = 2nCn/(n+1) * n! For unlabelled = (On Basis of Geometric Sturucture) T(n) = (2n)Cn/n+1 Right? What if its Asked for BST what will be the answer in both the above cases and Why?
asked Feb 17, 2018 in Algorithms Na462 196 views
...