Javascript Trees

A tree data structure is very similar to a linked list. Where linked lists are linear (meaning we have each node in the collection pointing to a next node in a fixed sequence), a tree data structure is non-linear. This means we can have each node potentially pointing to one or more nodes. Think of a trees as a way to order things hierarchically. Example are, graphical representations of data (like an organizational charts), files in a file system or even sorted collections of data. When working with trees, order of the elements is not important (if it is, you can store your collection in a linked list, stack, queue, etc). Lets take a look at an example of an organizational chart ( a type of tree structure showing hierarchical data ).

Here we see an example of an organization chart (which we are using to represent our tree). It represents a logical way of thinking about how things are structured in an organization. We are not interested, lets just say, in where one node is located in memory, but how it represents data logically. We can see who reports to who in this chart (hierarchy). For example the Team Managers report to the Program Manager who reports to the VP of Production, who then reports to the CEO of the company. The diagram help us make sense of complexity in the real world. Lets look closer at the various parts of this data structure.

Trees can be broken down into levels. Level 0 represents the root node. There can only be one root node in a tree data structure. Its the node with no parent (Node A is not derived from any other node). Going down the levels we have 1, 2 and 3 which represent child nodes. B, C and D are child nodes of A, but you can also think of them as parent nodes. For example B is a child of A, but E is a child of B. Because E does not have any children, we call E a leaf node. Nodes that exist on the same level are called Siblings. Just like your siblings are derived from the same parents. The link between nodes are called Edge. You can also have subtrees, which are cluster on linked nodes. For e.g B, E, F & J are a subtree where B is the parent of the tree. Pretty simple to understand. Now here is where things get interesting. Notice that we have 3 child nodes underneath Node A (the root node). While this is still a tree, there is another way of representing tree data structures where you have no more than two nodes children for every node. This is what we call a Binary Tree. From Binary Tress, we can derive Binary Search Trees (BST): A way of searching through tree data structures based on certain rules. We will be looking at that soon, but before that, lets look at Binary tree diagrams.

Lets try to make sense of this tree. I have 3 binary trees in the diagram. As you can see each node can have no more than 2 child nodes attached to it. It can have 0, 1, or 2 nodes only. Looking at figure A, the root node is 1. To the left of 1 is 3, and to the right is 4. We call 3 the left child and 4 the right child. Lets consider these numbers as key values for the nodes. Since each node is essentially an object in the collection, we will use these numbers to represent each nodes key. Now the rule when working with BST’s is that, when we add new nodes to the collection (starting at the root node), if a node is greater than the root, it goes to the right side of the tree. If its less, it goes to the left side of the tree. So looking at figure C, 56 is the root node. When we added 20 and 90, 20 went to the left, since its less than 56, and 90 went to the right. When we added 88, it also went to the right side as well. However since we already have 90 as a child, it goes to the left of 90 as its child. 95 was however placed to the right of 90, since its greater. This is how we add things to a tree data structure. So figure A and B only shows you the parts of a binary tree BUT it does not have rules applied to it. Now what happens when you add a value that is equal to the root node? The rule for that is to go in the direction of greater than (to the right). If i add 56, it would go to the right. When it gets to 90 it will branch left, and when it gets to 88 it will branch left again.

Now you might be wondering why use this way of arrangement? Well it turns out that by doing things this way, you can write programs that make inserting, searching and deleting data very efficiently! You might also be thinking: “thats what a Hash Table do!”. And you are right to think so. So why would we just use a hash table? Why do we have to implement a binary tree? Because it is a data structure that naturally remains sorted as you add child nodes. This is not so for Hash Tables. So if this is part of your application requirements, then this data structure might be best for you to use. Because BST’s stay sorted, we can get all the items in the tree in order, which can help to enumerate things in sequence (hash tables don’t give us that support). This uniqueness gives the tree its power to search. When its time to find a node, say 95. The tree naturally knows which direction to go in. This help eliminate searching other larger portions of the collection. For example in figure C, looking for node 40, the tree would start searching in the left side of the tree, eliminating have to look at node 90 subtree.

It not unusual to have a binary tree that is skewed as you add data (to the right or left). This produces a left skew or a right skew tree. Lets see how this is represented.

If you look at figure A, B or C it makes sense why there is a such a skew. In A, we have 5 as a root node and it only makes sense to insert nodes to the left based on the nodes values. The collection is skewed to the left. In C, they are skewed to the right. In B, we call this type a skew tree. We cant always guarantee that the structure will always be symmetrical. Some binary search tree implementations have algorithms which can help the tree to self balance. This helps balance the difference levels. Some algorithms used to balance binary trees are: Red-Black trees, AVL trees, Scapegoat trees, splays trees etc. Note these are not data structures, they are algorithms. We haven’t gotten to the algorithms section of this series yet. Before we start implementing our BST lets take a look at a diagram which will help us write our class.

The above diagram will give us an idea how we are going to code our BST class.Each node in a BST has a key value, as well as a pointer to the right and left child. It can have other properties (like a counter, etc).The class also has a root node. Lets use these ideas to construct a class.

Binary Search Tree Implementation

Lets write the basic shell of our BST.

See the Pen BST Shell by kofi (@scriptonian) on CodePen.

We are all familiar with this pattern by now (if you have been following up with my other data structure posts). Based on the diagram we create a class to represent nodes that we will add to the BST (TreeNode). We know that a node has right and left pointers, pointing to another node. We also know that each tree node has a key value. So we use this information and create the necessary properties on our class. We also created a toString method to help us identify the node. Next we create our main class, the BinarySearchTree class that will house tree nodes. It only has one property (the root node).

What we will be adding next are methods on our BST class. Some of the operations we will be looking at are insert, find, remove, maximum, minimum, and how to traverse binary search trees ( inorder, preorder and postorder traversal), many more. Lets add these to our shell structure.

See the Pen BST Shell Enhanced by kofi (@scriptonian) on CodePen.

Adding to the BST

With our shell in place, lets talk about our first operation. We are going to see how we add a node to our BST. We will do this using our insert method. Adding items to tree data structure is done by using recursive algorithms. The process in which a function call itself directly or indirectly is called recursion, and the corresponding function is called as recursive function. BST’s use algorithms such as these when adding nodes to the collection.This makes it efficient as the runtime complexities of recursive algorithms are O(log n). Lets take a look at this process.

When we try adding a node to a tree collection, the following scenarios are possible. The first is that the collection is empty. If its empty then the node we are adding becomes the root node. If the collection is not empty, then there is already a known root node. We must then use some rules to add this new node to our collection. If the node being added is smaller than the current root, it is sent along the left side of the tree (to the the left child of the root). And if an even smaller node is added, it is added recursively to the left. The means we keep calling a function, which continually places the node in the left side.

Another scenario that could happen is that we add a node that is larger than the root node. When this happen the node will be added as a right child to the root node. And adding larger values will be added recursively to the right as well. What if we add a value that is already in the tree? When this happens, we are going to treat it as a larger value. Remember we only have two directions we can move in. Either we send it to the right or left. So equal values are sent on the larger than path (to the right side recursively). I think i have over explained here. Ready to write some code? Lets do it!

insert()

The first method we will implement is how to add new nodes to a BST data structure. Lets take a look at the insert method.

See the Pen BST – Insert by kofi (@scriptonian) on CodePen.

When insert is called, we first create a new TreeNode with the key value passed in. If the BST root is null, then the collection is empty and we have to assign the passed in key value as the root node. If it is not null, then we call our recursive function to do the insert operation. This function takes a node where we want to do the insertion. We called this the positionNode in our code (call it whatever you want). When this function is called, it first checks to see if it should insert the to right or left side of the tree. When that is determined it checks if the position nodes left or right property is null. If its null then we have an opportunity to assign to the left/right property, if not it means the left property is already taken. We call the insertTo function again. However this time we want to call insertTo with a different position nodes (since we keep traveling along the node path till we find where to insert).  Finally we increment the count (helps us know how many nodes there are in our collection). Take a closer look at the code and let us test our insert function. Lets create a BST with these numbers: 60, 30, 85, 95, 80, 35, 20 (which look like this after we apply our rules).

Now lets see if we can see this same relationship in our console if we insert this numbers into our own BST. First our test code:

See the Pen Binary Search Tree – Insert Test by kofi (@scriptonian) on CodePen.

Here is our console log.

We see we have a total count of 7, which represents the number of nodes we have in our collection. The root node has a key value of 60, which was the first item we added to our collection. Then we added 30 and 85. Since 30 if less than the root node 60, it goes to the left side and 85 goes to the right. In the console you can also see the child properties of 30 and 85. For example in our diagram 95 is the right child of 85 (exactly what our console reports). This means our insert is working. Go ahead and add more nodes to verify that it works for levels more than 2. Lets move on and learn how to traverse our binary tree.

Traversing a Binary Search Tree

Traversing is something we do on a daily basis as software engineers. When working with collections of data, there is always a need to iterate through them. Traversing a BST means running through all nodes in the collection and performing an action on them (for example printing all key values). It turns out there are 3 traversal functions when working with BST’s (thats moving through the tree in a particular order). The first visits all nodes in the collection, in order as ascending key values. We call this the inorder traversal. This traverse makes a lot of sense and i don’t really need to explain why we might want it. The other two preorder and postorder are quite weird in the way they operate. Preorder traversals start at the root node, then traverses all the nodes to the left child of the root node (left subtree or branch – A subtree/branch are nodes underneath the root). Then finally, it traverses all nodes to the right child of the root(right subtree). Postorder starts by traversing children of the left subtree, then through the right subtree. After that it ends on the root node last. Here is a summary of the 3.

InOrder – Start from left subtree in order (smallest) all the way to the root (middle), then traverse the right subtree to highest value.
PreOrder –  Start from the root node. Then traverse the left subtree and then traverse the right.
PostOrder – Traverse the left subtree, then traverse the right, then finally end on the root.

Lets take a look at a diagram that will help us understand even more.

We will use the above diagram to illustrate the tree traversals we are talking about.

Inorder (Left Subtree [4, 2, 5], Root [1], Right Subtree [3]) -> 4 2 5 1 3
Preorder (Root[1], Left Subtree [4, 2, 5], Right Subtree [3]) – 1 2 4 5 3
Postorder (Left Subtree [4, 2, 5], Right Subtree [3], Root[1]) – 4 2 5 3 1

So our algorithms will recursively search in this order. For example, for the inorder function, we will first traverse the left subtree, then we will visit the root node, then finally we will traverse the subtree. In each traversal, all we want to do is print out the node values. We will use our toString method we wrote on our node. All we have to do is call this method in our function to output the value.

Lets first take a look at the inorder function.

See the Pen BST Traversal – inOrder by kofi (@scriptonian) on CodePen.

The code is nicely commented so you can see each step of the algorithm. You can see when the left & right subtree is being recursively iterated. But if you are like me, you might be wondering what all this magic is! You sort of understand what the recursive code might be doing but you don’t get it 100%. One thing is clear form the code however; when we called inOrder we pass it the root node of our BST. That sounds simple enough. We pass the root because the root has all the child nodes. We check to make sure the passed in root node is not null (otherwise we have nothing to work with). Somewhere in the code we print out the string value of the node using the toString method. I believe the secret to understanding what is going on with the recursive calls is to understand how call stacks work with function calls. This is something that happens naturally in javascript. When you execute a function, its put it onto the execution stack. So as we call functions recursively understanding this stacking order will take you far.

Let us step into what inOrder is doing with an example binary tree we used earlier ( 60, 30, 85, 95, 80, 35, 20 ). Please see the diagram below.

We saw this earlier in an example. The only difference here is that i have added NULL nodes to the leaf nodes (these are already there implicitly). I am adding them here for demonstration purposes only. I have also outlined our inOrder function and made a little note at the bottom. Take note of code lines X, Y, & Z (i  will be referring to them regularly). During recursion, each time inOrder is called it attempts to execute each line in the function. Not only that, each function call during recursion is actually put on the execution stack. You can read more about this in my introduction post on javascript promises (first 3 paragraphs). So when we call inOrder with the 60 node ( the root node ), it’s put onto the execution stack. Take a look at this diagram

See the Pen Binary Search Tree Traversal by kofi (@scriptonian) on CodePen.

I could almost cry at how beautiful that code looks. So simple, yet so complex! I really pulled my hair understanding how this works so i could explain it to you. So kudos to you in you understand it (it means i did a good job explaining it). With time it only looks easier. So if you don’t fully grasp it, keep reading and re-reading, watch youtube videos. I particularly liked this one ( though its in java ). Lets complete our binary tree by implementing our find and remove methods.

Find / Search

A BST is a very efficient structure for finding data. Because it is self organizing the structure is able to discard large amounts of it data because it already knows how to priority search. On its farthest left, you find the smallest value. And on the farthest right, you find the maximum. This means that to find the max and min, you would only have to keep traveling in either direction, searching till you find the furthest right or left. To find specific values however we would have to start from the root node, and apply a few rules. First we check to make sure that the current node is not null, if so we return from the function with a null. If the current value we are looking for is equal to the current nodes value, then we return that node. Otherwise if the value we are looking for is less than the current node, then we recursively call our function to return the value. Otherwise the value is greater and we recursively search the right side of our tree. Lets take a look at the code.

See the Pen Binary Search Tree – Searching by kofi (@scriptonian) on CodePen.

This should all be self explanatory. Do ask questions if there are any. Lets move to our last method!

Removing

Now for the last method. We saved the hardest method for the final showdown! Remove is the most complex method when working with BST’s. So brace yourself. Here is how we are going to delete a node. First we find out if the node exists. If it doesn’t exist, we just exit the function. Simple enough. We can easily use our find method to do this (so we have done part of the work already). If the node to be removed exists, then perhaps it might be a leaf node. In that case we remove its parents pointer to the deleted node. In other words we return null to its parent (which gets garbage collected). This means that we have to keep track of the node we are deleting’s parent (which we have not done so far). Finally, if it is not a leaf node, then its possible it has one child node or 2 node children. If its got one child, we need to send the current nodes child to its parent. But even having one child depends on where the child is located(is it to the right or left?). This may be a little hard to visualize so lets draw a diagram.

Here are the test cases we will be looking at. Lets just say the node we want to remove does not have a right child. In the diagram above, the 8 node doesn’t have a right child(so does 2, 5 and 7 – so this applies to them as well). The 8 node has a left child, and that is the node we want to remove. What we do in this case is promote the left child into the 8 nodes place when we delete. See diagram for before and after (b). Lets look at what happens if the if the node has a right child that does not a left child.

If the node to be removed, for example the 6 node has a right child that has no left child. Then the right of the 6 node is shifted up (like you see in the diagram). Finally what if the node we are removing has a right child which has a left child. In that case, the right child’s left most child node will replace the removed node.

This case is quite unique. The node we wanted to remove is the 6 node. But that node has a right child who has a left child (the 7 node). In that case the 7 node is promote to the deleted node spot. As you can see, its involving to write such logic (there is a lot going on). But lets give it a try anyway. Ultimately it all begins by finding the node we want to delete. Lets take a look at the code.

See the Pen Javascript Binary Search Tree – Remove by kofi (@scriptonian) on CodePen.

As you can see, removing a node from a BST is no joke at all and i wouldn’t want to get asked in an interview question. The solution does not use recursion, however i have provided one in the github repo called delete (use whichever one suits you, though i think the recursion solution is a bit more elegant – few lines of code). The algorithm is also slightly different, but the results are still the same.

We are learned quite a lot about binary search trees. If you are interested to learn further i would advise to study Adelson-Velskii and Landi’s Trees (AVL) and Red-Black trees. The reasons for having these is because these trees are self balancing. When working with trees there are chances your tree grows in a skewing manner. Meaning one side of the tree will be longer (we spoke about this earlier). This can lead to performance issues and thus these two balancing algorithms are there to solve this problem. We will not be look at them in this post. But i might consider extending this post in the future to include them. We have learned to add and remove, search, traverse when working with binary search trees using our language of choice – Javascript. Lets wrap up this series by talking learning one more data structure: Graphs. Until then, see ya! Feel free to reach out on twitter as well ( @scriptonian ) if you have any questions.

1. Aminu Abdul Manaf

Snippets now cool requires horizontal scrolling though.

1. scriptonian

Hi Amin, horizontal scrolling works both on android and ios. i tested myself. what device are you using?

2. really mind blowing!

1. scriptonian

thanks for reading 🙂 was a pleasure writing this… and glad you like it 🙂