In this guide we're going to walk through an overview of one of the most popular types of binary trees, the binary search tree.

To make the concept of binary search trees a little more concrete let’s begin with a high level view of what binary search is from a real world example. Imagine that we lived in a world that still used printed dictionaries.

What would the algorithm look like to find the word “Motorcycle”? We could go with the naive approach and start at the beginning of the dictionary and look at each word until we get to “motorcycle”. However that would force us to traverse thousands of words for no reason. That’s not the way that we’d lookup a word in the dictionary, so that’s probably a good indicator that there’s a better option in the computer science world as well. How would you find “motorcycle” in the dictionary? You’d open the dictionary up in the middle, if you landed on a page where all the letters begin with “O” you would know to flip to the left, if you run into the “L’s” you know you need to move slightly to the right. You’d continue this process until you found “Motorcycle”.

So binary search is faster than simply going word by word, but how much faster is it exactly? I'm going to give you the technical answer, but let it scare you away if you've never heard of this type of terminology.

Binary search runs in O(lg n) time complexity.

This is very fast, in fact, even if you used binary search on a dictionary with millions of hypothetical words you’d be able to find the target word in around 20 page turns. This would be compared with the naive approach that would take tens of thousands of page turns.

So now that you have a good idea on how binary search works at a high level, let’s walk through a technical example. Imagine you had an array of values such as this:

[1, 2, 4, 4, 4, 5, 6, 6, 7, 8, 9, 10, 20, 19, 17, 22, 30, 75]

How would we find the 19 value? Keeping our dictionary example in our mind, we’re going to utilize the same principle to quickly find the 19 with binary search.

Here you can see what a binary tree looks like. There are a few rules that binary trees need to follow in order for us to search through them:

• Each node has the ability to have, at most, two child nodes.
• The child node on the left has to be less than the parent node
• The child node on the right has to be greater than or equal to the parent node

As you can see this tree obeys each of these rules, which means that we can utilize binary search to find the 19 value. The process is as follows:

1. We start at the root node, in this case it’s 10, and since the target value is greater than 10, we can immediately ignore the left side of the tree, cutting our collection by over 50% right away.
2. Looking at the value 20, we know that 19 is less than 20 so we move to the left.
3. Lastly we see that we’ve arrived at the target value and our search is over.

This only took 3 comparisons to get to the 19 value, which is much faster than if we had simply started at the beginning of the array and iterated through it until the target was found.

Obviously with a small array like this it would be easy to iterate through and get the 19th value. However this is a base case, binary search makes it possible to search through millions of values in an efficient manner.

Summary

In summary, some keys to remember for understanding binary search trees are as follows:

• Binary trees are a data structure
• Each node can have up to two child nodes
• To search through the tree you recursively traverse the tree and move left for lower values and right for greater than or equal to values
• Binary search runs in O(lg n) time complexity

What's Next?

In the next guide we're going to dive deeper into binary search trees, including walking through how to build a tree from an array.