Binary Search Tree

Posted on December 1, 2018

Binary search tree, also known as an ordered tree, is a phrase that you will see a lot when discussing Computer Science, or looking at leetcode discussions. its a root node, whose leaves and branches on the left are lower in value than the root, and the leaves and branches on the right side are higher than the root. In simple terms, left is less than, right is greater than.

The Binary Search Tree is a data structure that is used for performing lookups. The strength of a BST (Binary search tree) is that when performing a lookup via comparisons, it allows you to drop half the values in the data structure every time you make a comparison. WHen doing this over large data sets this can potentially save a lot of time and searching. The complexity of the BST would be O(log n), where over time as the data set grows, the search timed does so miniscule. Compare this to a linear search algorithm, where we would start at the beginning of the data structure, and iterate over it until we found the value desired. As the data set grows so does the amount of time it takes to go throw that set.

If you aren’t familiar with linked lists, than you should go over that first, because a BST is like a link list on caffeine! When creating a node of a BST, generally, the node will have these properties, a value, a left pointer, and a right pointer. So instead of a next for linked lists, we can traverse the tree by going left or right. Each path that you take is a branch.

The best way to wrap your head around why the binary search tree is the classic phone book example. Let’s say you were looking for Larry King. There is a bookmark for the middle of the phone book. You open it and it has the name Might Mouse. Ok, so King must be to the left of mouse. Anything after Mouse, we can ignore. Now we estimate the middle of A-M which would be around the letter G, so we see that there is a bookmark at G, and we find Garry Golden. Hmm, King would be after Golden, so now we ignore A-G. So from G-M we go to the middle and see a bookmark at J. We turn to J and find Michael Jordan. Hmm, K comes after J so now we look between J-M, and we end up between K and L. Ok so the name we have is John Kzrinsky. Ah, ok it must be to the left. We found Larry King! And that is how a BST would operate.