What is a Binary Search Tree?
Try finding a simple explanation of what a binary search tree (BST) is, and you’ll probably be disappointed. How do I know? Because I tried, and failed.
Most of what I came across was more complicated than what I was trying to find. Many articles even go into a good amount of detail about the algorithmic complexity of insertions, finds, tree balances, so on, and so forth. This article is not that. I’m going to just start from scratch, and leave languages and algorithms out.
Instead, we will focus on:
- What a tree is
- What makes a tree a binary tree
- How data is stored in a tree
- What makes a binary tree a BST
- How to search for and insert values into a BST
- Why BSTs are useful
What a tree is
Let’s talk about nature. A tree in the wild is just a big piece of wood (a branch that is normally called a trunk). That big piece of wood can have smaller pieces of wood that come off of it (branches). Those branches can have leaves.
Similarly, a tree in data is just a trunk, which we call the root. Its branches are called subtrees (since those branches can have subsequent branches as well) or nodes.
If a subtree has no children (no branches off of itself), we call it a leaf.
What makes a tree a binary tree
Once you wrap your head around trees, binary trees are a bit easier to understand. A binary tree is just a tree whose nodes (the circles) have a maximum of 2 subtrees (or children).
The root node in the example above has 3 subtrees (one with children, and two without), so that example is not a binary tree.
How data is stored in a tree
The key thing to know about the tree data structure is that each node on the tree has a value associated with it. No nodes are allowed to be empty. If a node doesn’t have a value, it just doesn’t exist.
Below is an example of what I mean by that.
What makes a binary tree a BST
You may have noticed something special about the tree above. Each node has two children. Left and right. But each node’s left child is smaller than the node’s value, and each right child is larger. This is what makes a binary tree a binary search tree.
How to search for values in a BST
As the name might suggest, a common use case of a binary search tree is to search if a value exists. Lets look at an example:
How to insert values into a BST
It’s also useful if you can add things to a tree. Doing that is actually pretty easy, and looks a lot like searching. You start at the root. If the value you want to insert is less, go left. If it’s more, go right.
One caveat is that you should never insert a value that already exists. BTS’s can’t have duplicate values, because a value is not greater or less than itself! To prevent this, at each step along the way, just check to make sure the value you’re trying to insert doesn’t equal the node you’re currently looking at. If it does, just throw an error or do nothing at all. Your choice!
Why BSTs are useful
It all boils down to the speed of these search and insert operations. Without going into math, just know that the speed at which inserts and searches happen are, on average, very fast.
Searches and inserts only touch a small amount of the items in the structure (which I highlighted in red). This means that there are less comparisons happening, and less work being done.
Conclusion
Binary search trees are a very powerful (but not perfect) data structure to have in your programming tool belt. If done right, handling large amounts of sorted data becomes easier and quicker.
For a cool animation on how the operations mentioned here work, check this out. For further and more in-depth reading, check this out.
I hope this article has been helpful for you. If so, let me know by giving me some claps, leaving a comment, or hitting me up on Twitter!
