## A Guide to JavaScript Algorithms — Graph and Tree Traversal

January 01, 2019

A Guide to JavaScript Algorithms — Graph and Tree Traversal

Algorithms and data structures have always been connected together. Without data structures, we would not have any objects by which we can implement our logic to solve the problem statement, and without algorithms, our objects cannot be consumed.

An algorithm is a function that takes in some data structure as input and manipulates it into some kind of output. The type of output that we get is based on the logic of the algorithm. To do all this, it is important that the developer clearly understands the problem statement and what is asked of him.

Understanding the logic behind the algorithm is fairly easy. things get more complicated when you are required to turn the logic into actual code.

In this post, we will take a look at some the common traversal algorithms in JavaScript. Some of these are very commonly asked in coding interviews, while others are not so common and will usually make you scratch your head in order to solve them.

Tip: Discover and share JS components in Bit’s component platform, and use components like Leko to build applications faster with your team. Give it a try.

Breadth first is an algorithm that is used to search for a node in a graph data structure. The algorithm starts at one node, then goes to its neighboring nodes. If the node we are searching for is not found, then it will go to the next node look at its neighbors.

This algorithm also uses the queue data structure to make note of all the nodes that it has visited. This way, the algorithm will save time by skipping the already visited nodes.

Let’s start by writing the queue, node, and graph creator functions as shown below:

Inside the `graphCreator` object, we will create a `breadthFirst` method that takes in two arguments. The first argument will be the `id` of the starting node and the second argument will be a function that gets called everytime we visit the node’s neighbors.

We will use the `reduce` function on the `nodes` array to reduce it to an object where each `id` is the current node’s `id` and the entire value is set to false. It will be set to true when the algorithm visits the corresponding node.

After that, we will keep make a note of all the nodes that we need to visit by using the `queueCreator` function. The traversal algorithm will only work `while` this queue is not empty. So we will fill the queue with the `startingNode` and its neighbors.

Every time the `while` loop ends an iteration, we will remove a node from the queue and set it as the `currentNode`. If the algorithm has not visited that node before, then we will call the `neighborVisit` function and set its value to `true`.

Enough talking, lets write the code as shown below:

`breadthFirst(startingNode, neighborVisit) {  const firstNode = this.searchNode(startingNode)  const visitedNode = nodes.reduce((sum, node) => {    sum[node.id] = false    return sum  }, {})  const queue = queueCreator()  queue.add(firstNode)   while (!queue.empty()) {    const temp = queue.remove()    if (!visitedNode[temp.id]) {      neighborVisit(temp)      visitedNode[temp.id] = true    }    temp.neighbors.forEach(node => {      if(!visitedNode[node.id]) {        queue.add(node)      }    })  }}  `

We can now test the algorithm out by creating a graph data structure first. As shown below:

`const graph = graphCreator(true)graph.addNode('a')graph.addNode('b')graph.addNode('c')graph.addNode('d')graph.addNode('e')graph.addNode('f')graph.addEdge('a', 'c')graph.addEdge('a', 'e')graph.addEdge('b', 'a')graph.addEdge('b', 'c')graph.addEdge('c', 'd')graph.addEdge('c', 'e')graph.addEdge('d', 'e')graph.addEdge('e', 'f')graph.addEdge('f', 'e')`

The graph created here would look something like this:

We can now use the `breadthFirst` method to print the node ids as in the order in which the algorithm arrives at the node, as shown below.

`graph.breadthFirst('c', node => {  console.log(node.id)})`
`// Outputcdef`

Here the algorithm starts with the node `c`. This node is connect to nodes `d` and `e`. So, the algorithm will print out the nodes `c` followed by `d` and `e`. Next, the algorithm will look at the neighbors of node `d`. Node `d` is only connected to `e`, which will be ignored by the algorithm since it is already visited. The algorithm will now look at the neighbors of `e`. Node `e` if only connected to node `f`, which the algorithm will print out in the console.

Depth first algorithm is a traversal algorithm that starts searching at one node, and then goes down the path of its neighboring nodes before it goes to the other paths.

Lets go to back into the `graphCreator` object and create a new method named `depthFirst`. Similar to the `breadthFirst` method, this method will also take two arguments, one to define which node to start the traversal from and the other argument is a function that will be called as the algorithm visits each node for the first time.

`depthFirst(startingNode, neighborVisit) {  const firstNode = this.searchNode(startingNode)  const visitedNode = nodes.reduce((sum, node) => {    sum[node.id] = false    return sum  }, {})  // Write the next code here}`

In the depth first algorithm, if there is another level to go down, then the algorithm will `travel` down that path first. We will create a function named `travel` that will check if the node in that path was already visited. If it was, then the algorithm will return nothing. Else, the algorithm will call the `neighborVisit` function and mark the node as visited by setting the `sum[node.id]` value to `true`. We will also loop through all the neighbors of the node and call `travel` on them, and we will start the algorithm by calling `travel` on the `firstNode` as shown below:

`travel = (node) => {  if (visitedNode[node.id]) {    return  }  neighborVisit(node)  visitedNode[node.id] = true`
`  node.neighbors.forEach(neighbor => {    travel(neighbor)  })}travel(firstNode)`

Our algorithm is now ready! Let’s test it out on the same graph that we used for the breadth first algorithm.

`const graph = graphCreator(true)`
`graph.addNode('a')graph.addNode('b')graph.addNode('c')graph.addNode('d')graph.addNode('e')graph.addNode('f')`
`graph.addEdge('a', 'c')graph.addEdge('a', 'e')graph.addEdge('b', 'a')graph.addEdge('b', 'c')graph.addEdge('c', 'd')graph.addEdge('c', 'e')graph.addEdge('d', 'e')graph.addEdge('e', 'f')graph.addEdge('f', 'e')`

Calling the `depthFirst` method on the graph with node `a` as the `startingNode` will give it the following output

`graph.depthFirst('a', node => {  console.log(node.id)})`
`// Outputacdef`

Node `a` is first connected to node `c`, so the algorithm will travel down this path first. The node `c` is then connected to node `d`, which is connected to node `e`, which is finally connected to node `f`.

A binary tree is a tree data structure where each node can only have upto two child nodes.

To start, we will write a node creating function that will take the `id` as an argument. It will also have a `left` and `right` properties that are initially set to `null`. Also, we will write methods to add child nodes, one to the left path and the other to the right path as shown below.

`nodeCreator(id) {  return {    id,    left: null,    right: null,    addToLeft(leftId) {      const newLeftNode = nodeCreator(leftId)      this.left = newLeftNode      return newLeft    },    addToRight(rightId) {      const newRightNode = nodeCreator(rightId)      this.right = newRightNode      return newRight    }  }}`

We now get to the traversal part of this section. A binary tree can be traversed in three ways:

• In-order
• Pre-order
• Post-order

These three are actually quite similar to each other. Each of them will receive a starting node and a recurring function that the algorithm will use to traverse through the binary tree. First, let's create an object that will store the code for these traversal processes.

`const algorithms = {  IN: () => {},  PRE: () => {},  POST: () => {},}`

The in-order traversal algorithm first travels down the left branch, then goings to the current node, and then goes down the right branch. To code this algorithm, we will call the `IN` function recursively as shown below:

`IN: (node, func) => {  if (node ! null) {    processes.IN(node.left, func)    func(node)    processes.IN(node.right, func)  }},`

The pre-order algorithm first visits the current node, then travels down the left path, and then travels down the right path.

`PRE: (node, func) => {  if(node ! null) {    func(node)    processes.PRE(node.left, func)    processes.PRE(node.right, func)  }}`

The post-order algorithm is the complete opposite of the pre-order algorithm. It travels down the left path first, then it travels down the right path, and finally visits the current `node`.

`POST: (node, func) => {  if (node ! null) {    processes.POST(node.left, func)    processes.POST(node.right, func)    func(node)  }}`

We still need to write the binary tree creating function. All trees have a root node. So, this function will first receive a `rootId` as an argument, using which it will create a node named `root`.

The `display` function is going to take the traversal `type` as an argument, with its value set to `IN` by default. The function will have a variable named `output` initially set to an empty string. We will then create the function that traversing algorithm use to go through the tree. Basically, when the algorithm visits a node, its `id` will get added to the `output` string.

`binaryTreeCreator = (rootId) => {  const root = nodeCreator(rootId)  return {    root,    display(type = 'IN') {      let output = ''      const func = node => {        output += output.length = 0 ? node.id : ` => \${node.id}`      }      processes[type](this.root, func)      return output    }  }}`

And we are done! Now to test the traversal algorithms, lets first create a binary tree as shown below:

`const binaryTree = binaryTreeCreator('a')const b = binaryTree.root.addToLeft('b')const c = binaryTree.root.addToRight('c')const d = b.addToLeft('d')const e = b.addToRight('e')const f = c.addToLeft('f')const g = c.addToRight('g')const h = d.addToLeft('h')const i = d.addToRight('i')`

The binary tree that built from the above code will look something like this:

The traversal algorithm can be used in three ways. The first way, we don’t pass any argument to the display method. That way, the algorithm will run the in-order traversal as shown below.

`console.log(binaryTree.display())// outputh => d => i => b => e => a => f => c => g`

If we pass the `type` argument to the display method and set its value to `IN`, we will get the same output.

The second way will require us to pass the `type` argument with its value set to `PRE`. The algorithm will then run the pre-order traversal as shown below:

`console.log(binaryTree.display(type = 'PRE'))// outputa => b => d => h => i => e => c => f => g`

The final way will have us pass the `type` argument with a value of `POST`. The algorithm will then run the post-order traversal as shown below:

`console.log(binaryTree.display(type = 'POST'))// outputh => i => d => e => b => f => g => c => a`

In this post, we took a look at some of the most common traversal algorithms in JavaScript.

We started with the breadth-first algorithm, where the algorithm starts with a node, then explores its neighbors, and then moves to the next level of nodes.

Then we took a look at the depth-first algorithm, where the algorithm starts with a node, explores each of its branches, then backtracks to other nodes.

Finally, we saw how to build a binary tree and the various ways we can traverse through it.

In order to keep this post short and to a point, I have only focused on traversal related algorithms in JavaScript. But even then, there are many other algorithms in JavaScript. You can check out this repository maintained by Oleksii Trekhleb to learn about other kinds of algorithms that you can code in JavaScript.

Thanks for reading this long post! I hope this post helped you understand JavaScript Algorithms a little better.If you liked this post, then please do give me a few 👏 and feel free to comment below and chat! Cheers