When Binary Search Tree can perform worst?

We all know that a binary search tree operations are of O(log n). But there can be a worst scenario where it can go up to O(n).

So you might expect quick question like,

When can binary search tree perform worst?
What type of data can not be a good bet to use to form a Binary Search Tree?
What can go wrong with Binary Search Tree?
Binary search tree worst case scenario.

Answer is easy:


Unbalanced binary search tree can perform worst in a special case like sorted data.
If all the data are coming in a sorted order and forming BST then our tree will be unbalance and it will be form a linked list type of structure only as shown in the above figure. So this structure is equivalent to a singly linked list which makes the operation of search/remove/insert O(n).

Leave a Reply

Your email address will not be published. Required fields are marked *