# Binary Search Tree

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)
0
For which operation? Searching?

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

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
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?
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?