While it’s true that on average a BST has O(log(n)) lookups, deletions, and insertions, that fundamental benefit can break down quickly.

If mostly sorted data, or even worse, completely sorted data, is inserted into a binary tree, the tree will be much deeper than it is wide. As you know by now, the complexity of the tree’s operations depend entirely on the depth of the tree.

A balanced tree will always have the minimum height possible for the number of elements it contains.

References

• boot.dev

Next -> red-black-tree