Binary trees are important to know whether you are a budding developer, or a back-end engineer fine-tuning performance. It is a fundamental family of data structures used in computer science to visualize various datasets. In this blog we’ll go over a high level view of binary trees and some of their implementations in JavaScript. You can see my full repo here, in which I have begun coding out other data structures such hash tables and linked lists, which I plan on blogging about over the next couple of weeks — https://github.com/mega0319/data-structures
Binary trees tend to be recursive in nature. Think about it. The tree starts at a root node and must adhere to the rule of only having up to two child nodes. The left child and the right child. So if a node can have only two children, how do we get the larger trees?
Well, each child node in this example can also be a parent that has two child nodes of its own. The left child and right child are known as sibling nodes.
So each tree can be composed of many subtrees. Nesting trees in this manner are the reason why we can write search and sort algorithms recursively, which we’ll take a look at later.
Another example of a binary tree
This tree has the root-node of 2 and has two child-nodes 7 and 5. Node 5 has one child, 9, which has a child of its own, node 4. Node 7 has two children of its own, 2 and 6. You get the point.
Coding Binary Search Trees in JS
Binary search trees are powerful constructs. We can organize and store data in them and use powerful methods to traverse them.
Binary search trees are a type of binary tree that are organized in the following way:
The value of each left child node must be less than its parent node.
The value of each right child node must be greater than its parent node.
An example of a binary search tree.
Implementing data structures in actual code will help you solidify your understanding of the structures. I highly encourage you to do so if you have even the slightest bit of curiosity.
Let’s build out our constructor function for the binary search tree first.
constructor function
Voila! Easy enough. We have our binary search tree constructor function. We pass in a value for the tree and set its left child and right child to null, as we know that a binary tree can only have a maximum of two child nodes. This was the easy part. Let’s add more functions to the prototype.
The next function we will build out is insert. This will allow us to add nodes to our binary search tree. We will use recursion to do so. As I had mentioned earlier that binary trees are recursive in nature and we can do very powerful things with recursion in just a few lines of code.
insertion function
In this function, the first thing we check for is whether the value we are inserting is less than or equal to our root node. If it is less, then we will check to see if our root node has a left child. If it does not, we will hit our base case and create a new binary search subtree in that location. If there is a left child node, we will hit our recursive case and call insert again, but this time on the left child node in question. If you are familiar with recursion this will make sense. If not, I suggest you take a look at my blog on recursion here.
Insertion in binary search trees have a logarithmic run-time of O(log n).
If the value is not less than or equal to our root node, we traverse the right side of the tree. Technically, I could’ve used an else statement here but for specificity, I wanted to be explicit.
Ok, next we will build out our contains function.
contains function
Our contains function will search through our binary search tree and return true if it finds the value passed in, and false if it does not. Notice that this is also a recursive function. We have our base case, which will check to see if the current node value is equivalent to our search value. Then we check to see if the search value is less than or equal to the root node’s value. Similar to our insert method, we will recursively traverse the tree in search of the value. Binary searches like this also have logarithmic run-times and have an O(log n) time complexity. Great! Now we can insert nodes into our tree and search it. What’s next?
Traversing the Tree
What if we wanted to touch on every node in our trees? If we are able to touch every node, we would be able perform some function on the nodes, such as printing each node out. We will implement two ways to achieve this; using depth-first search and breadth-first search.
Depth-First Search
In depth-first search, you start at the root node and traverse a branch all the way down to the bottom most node or leaf node.
depth-first search
Here is one implementation of depth-first search.
depth-first search function
Our depth-first search function has two parameters: iteratorFunc, and order.
As you can see, we are utilizing recursion once again. Order types aside, if our root node has a left child node, it will call the function. The base case is implied as if there are no more left child nodes, it will no longer call the function. Depending on which order we pass in, it will call our iterator function at different points in time.
There are three different types of depth-first search methods:
- Pre-order — hits the current node data before traversing both left and right subtrees
- In-order — hits the current node data after traversing the left subtree but before the right subtree
- Post-order — hits the current node data after traversing both left and right subtrees
Our iterator function is a function we can pass in. This function can take action on each node as we traverse the tree. We can use something as simple as this.
iterator function
Breadth-First Search
In breadth-first search, we traverse each level of the tree systematically before moving on to the next level of the tree. Here is an example of how that looks.
breadth-first search
breadth-first search function
Oh look, a while loop! To implement breadth-first search, we first set an array, “queue”, to have on element, ‘this’. ‘This’ is basically the root node. Our while loop will run as long as there is something in the queue array. Once in our while loop, we will shift the first item out of the queue, and set it to treeNode. We will then run out iterator function on this node. Once this is complete, we will check for left and right subtrees and push them into the queue. This will sweep the tree level by level and hit each node accordingly, until there are no nodes left. Brilliant!
DFS vs BFS
There are many different use cases for DFS and BFS. Let’s say we built a family tree and stored it in a binary search tree structure. Each family member node also had an attribute that held data on whether or not the member is deceased. We want to find all the members that are still currently alive. In this case, depth-first search would be a good solution since we want to traverse to the deepest possible node or leaf node of each branch and the data we want is most likely deeper in the tree.
What if we wanted the ancestors instead? If this were the case, then we want to collect all the nodes that are up near the top or the root node. It would be better for us to sweep the tree level by level via breadth-first search here.
Min/Max
The last couple of functions to wrap up our binary search tree would be to find the minimum value, and the maximum value. Since binary search trees must adhere to the rule of left child node being less than parent node and right child node being greater than the parent node, we can easily conclude that the smallest value in the binary search tree must the bottom-most-left node of the tree. The maximum, then must be on the bottom-most-right. Here is the code to implement those two functions.
minimum value function
maximum value function
And with that, hopefully I was able to help you better understand how binary search trees work, and how we can implement them in JavaScript. As you can see, these data structures, with the average case for accessing, inserting, searching, and deletion being O(log n) across the board, along with its recursive nature, make it a powerful tool that every programmer should have in his or her toolkit.