Build a Binary Tree in JavaScript and Several Traversal Algorithms
A binary tree is a tree where each node may only have up to two children. These children are stored on the left and right properties of each node.
When traversing a binary tree, we have three common traversal algorithms: in order, pre-order, and post-order. In this lesson, we write each of these algorithms and explore their differences.
Instructor: [00:00] Binary trees are trees whose nodes can only have up to two children, hence, the word "binary." We'll use a function to create our binary node object. A binary node receives a key as an argument and has a left and right property set to null. It also has the methods add-left and add-right.
[00:21] Add-left and add-right both receive a key. We create a new node from that key. We update the left and right properties respectively and then we return the new node. Now we can create our binary tree factory function.
[00:37] Since trees must have a root, our function receives a root key as an argument. We can then create the root node using our node factory function when we pass this to the object we return from the function.
[00:50] Now binary trees have three specific types of traversals -- in-order, pre-order, and post-order. I'm actually going to turn these traversals into an innumerable. Each item in our innumerable will represent the corresponding traversal type, and the value for each item will be a function that we can use to traverse our tree with.
[01:12] Each of these traversals is quite similar. They each have the same function signature. They receive a node and a visiting function. Because these are called recursively, they each have the same guard statement. We only want to operate if we know that the node is not null.
[01:29] We'll start with in-order traversal. In-order traversal starts by going as far down the left branch as possible, then visiting our current node, and then going down the right branch. The way we do this is to call our traversals in-order function recursively like so.
[01:46] Pre-order traversal is very similar, but we change the order in which we visit our nodes, and we change which traversal method we're using to traverse those nodes. I'm going to copy/paste the code from the in-order method to the pre-order method and make those changes.
[02:03] If pre-order means that we visit our current node first then it makes sense that post-order traversal means we visit our current node last. Allow me to copy/paste again to make those changes.
[02:14] Now that we have our traversal methods, let's add a print method to our tree, so that we can use these different traversals and see their output. We'll pass a traversal type as an argument into our print method, but we'll default that value to in-order since it's the most common traversal.
[02:31] We'll keep our print method pretty simple. We want to return a string, so we'll start by creating a result variable set to an empty string. Now we'll create a visiting function that when it visits each node, it'll concatenate the key onto our result string.
[02:46] We'll add a little touch where if there is no length in the current result, we only return the key. Otherwise, we'll attach a delimiter to our key.
[02:54] Now we can use the traversal type passed in on our traversals innumerable to get the right method to be used. Finally, we'll return a result.
[03:03] Now that we have a print method, let's try it out on a tree. I'm going to copy/paste some code in here to make a tree that looks like this.
[03:11] As you can see, our tree is a collection of letters from the alphabet. Why don't we try calling the print method on our tree and logging out the results with our different types of traversals.
[03:20] We'll start with the in-order traversal. If you remember, we defaulted it to in-order, so we don't have to pass in an argument. As you can see, we went all the way down to our left-most node, the H node, and then we began to work our way back up. It's why the A node comes in the middle because we visited that before we then traversed down the right side of our tree.
[03:41] Let's change our traversal type to pre-order and see the difference. As you can see with pre-order, the first node we printed is the first node we visited, the A node. We then went down the left side of the tree -- going all the way down B, D, and H -- going down each left branch before coming back and then going down the right branches.
[03:59] Now let's do our last traversal type and do post-order and see that difference. As you can see, we went all the way down the left-most branch getting to the H node again. We also went all the way down the right branch before we visited our current node A, which comes last.