Binary Search Trees
Hey guys, thanks so much for reading Think Like A Programmer where we break down complicated computer science concepts in bite-sized articles. In this week’s article, we’ll look at binary search trees - a useful data structure to filter and search for data in a convenient way.
Before starting on today’s topic, I highly suggest looking at our previous articles on
Analogy
Ever tried finding a book in a unsorted bookshelf? It’s pretty hard to find anything at all if the books aren’t sorted out nicely at all.
Most times, you’ll need to sieve through the books one by one until you find what you’re looking for and if you happen to accidentally gloss over the book that you want - good luck starting from the top.
That’s why most bookshelves are sorted out in a alphabetical order - you have the books that start with an A before those that start with a Z.
As we covered in our previous article on comparing algorithms, having an alphabetically ordered list of books means that we can reduce our search space.
Intuitively, If we’re looking for a book with a name that begins with a M, we’re not going to start looking for the book in the section with books that begin with Z.
What happens then as our collection of books gets larger and larger? Well, the most intuitive thing then is to simply start categorising collections according to subject. Each collection is then sorted alphabetically.