# doubt #DSA

Question

When and why AVL trees are preferred over Binary Search Tree ?

Answer 1

In BST, the time complexity of search operation (average case) is taken to be O(log n). But in the worst case, i.e the degenerate trees/skewed trees time complexity of search operation is O(n) which can also be attained using array or linked list. So, in order to remove this problem, balanced binary search tree (AVL tree) was introduced in which the time complexity of search operation remains O(log n).

Comments

"the degenerate trees/skewed trees time complexity of search operation is O(n) "means ??

---

if a binary tree is completely skewed like suppose you insert 5,10,11,12,14 in BST ,all nodes will be skewed to right

here we can't search in logn worst case time..we need to O(n) time to search

---

now i got it.