Skip to interview prep
Apexed

7. What is a binary search tree and why can it become slow?

MediumData structures & algorithms

Technical
Show model answer

In a BST every node's left subtree holds smaller keys and its right subtree larger keys, so search, insert and delete take O(height).

If keys arrive in sorted order the tree degenerates into a list and operations become O(n). Self-balancing trees such as AVL or red-black trees keep the height O(log n).

What is a binary search tree and why can it become slow — Software engineering interview question — Apexed