Binary Search Trees
Last week I started a segment looking React basics, I thought this week I take a little detour from React and look at another concept that is critical in implementing any kind of storing and scalability, data structures and algorithms. Data structures and algorithms are kind of a non starter if your doing a local project, not expecting to have multiple accounts logging in/out, accessing and storing data at the same time. It becomes more of an issue when you start live deployments of your code, how your users will go about accessing data, will be hindered based on the efficiency of how data is stored on the backend. I thought we start going down the rabbit hole of data structures and algorithms by looking at binary search trees, what are they? how is data stored and accessed? and what are they optimized for?
What Are They?
A binary search tree is just like it sounds, it has a root(a starting point) which then branches off into child nodes that contain a key and two sub trees referred to as the left and right node. For binary trees to be implemented successfully the left subtree’s must be less then the nodes key, while the right subtree’s key must be greater then the nodes key. This makes is what makes binary trees easy to traverse, the knowledge that when looking for a data point, the left will always be less then the right the further down the stack you go. For example, with the above binary search tree, lets say we were attempting to locate the number 28. We would start at the root node(25)and simply ask if 28 is larger then 25, since it is we will continue down the right of the root node. We would continue to do this with 36 and 30, since both of these are greater then 28 we would go left down the tree, where we would eventually end up at 28.
Traversing
The best part about binary search trees is how easy it is to traverse(iterate), this becomes particular apparent when we start to use recursion to drill down to the data point we need. I saw this example of recursion thru the use of Russian dolls at KhanAcademy, I thought it was a great use case to help explain how we can use recursion to traverse a binary search tree. Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. This is encapsulates(pun intended!) no better then in Russian dolls. Each Russian doll is a simpler(smaller) version of itself, and so on and so-forth. This in a sense is what we are doing with recursion.
search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return nodesource: Wikipedia.org
Above is an example of how you can make a search using recursion. Again this ties back to what we talked about in the beginning of how we can simply check each key and depending upon their values go further down the stack to get to the data point we are looking to access.
Optimize
Now that we have a pretty good understanding of the basics of a binary search tree and how to traverse thru them, what is a good use case? Well as we can see it is at its best when needing to compare values in (one being less then other being greater then) situation. Best example of this is numbers, being able to have a starting point to compare a number, then knowing to only need to go left or right to get to the number your looking for is some pretty sound logic. Below is some material I found helpful in understanding binary trees, thanks for reading, and happy coding!
