The Problem With Binary Search Trees

It's just a small, but important issue

A Binary Search Tree (BST) is a powerful tool for storing, managing, and retrieving data really quickly. And while it is a pretty robust data structure, it has a flaw. If for whatever reason data is inserted into a BST with the data keys already in order, the data will simply follow one side of the tree or the other straight out with no branches, looking much like the following.

This not only removes any of the value in using a BST, it is almost exactly the same thing as a linked list, meaning the complexity of adding, searching for, and removing data is now back to N and no longer Log₂N. If there is a possibility that a tree you are developing might encounter this circumstance, you should consider another data structure or strategy. Or . . .

As it turns out there is a way to handle this kind of problem by using a thing called self-balancing trees. And as it turns out rather conveniently, that is what you will be studying in the next chapter. Forward.