Home Programming Learn Javascript Algorithms: Graph and Tree Traversal

# Learn Javascript Algorithms: Graph and Tree Traversal

0
219

When it comes to two things that have traveled time and space together forever, Algorithms and Data Structures might come to mind. The Doctor and their Companion might be another. But the focus of this article is on Algorithms and Data Structures. Maybe some other time, ok?

What is an algorithm you ask? I’m glad you did, or this would be pretty short. 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. It’s important to understand clearly the problem and what is being asked of you.

The algorithms logic is pretty easy to understand. Where people often get hung up is converting that logic into code that you can actually use.

We’re going to look at a few of the more common traversal algorithms in JavaScript in this article. You’ll often find these in coding interviews. Some of these you likely won’t though.

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 it will travel to its neighboring nodes. If the node we are searching for is not found, then it will go to the next node and then 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.

``````queueCreator = () => {
const queue = []
return {
queue.unshift(x)
},
remove() {
if (queue.length === 0) {
return undefined
}
return queue.pop()
},
next() {
if (queue.length === 0) {
return undefined
}
return queue[queue.length - 1]
},
get length() {
return queue.length
},
empty() {
return queue.length === 0
}
}
}

nodeCreator = (id) => {
const neighbors = []
return {
id,
neighbors,
neighbors.push(node)
}
}
}

graphCreator = (uni = false) => {
const nodes = []
const edges = []
return {
uni,
nodes,
edges,
nodes.push(nodeCreator(id))
},
searchNode(id) {
return nodes.find(n => n.id === id)
},
const a = this.searchNode(idOne)
const b = this.searchNode(idTwo)

if (!uni) {
}
edges.push(`\${idOne}\${idTwo}`)
},
display() {
return nodes.map(({neighbors, id}) => {
let output = `\${id}`
if (neighbors.length) {
output += ` => \${neighbors.map(node => node.id).join(' ')}`
}
return output
}).joing('\n')
},
}
}``````

That is an awful lot of code, so let’s break it down for easier understanding.

First, inside the `graphCreator`object we create a `breadthFirst` method. That method will take two arguments as params. The first argument will be the `id`of the node that we are starting with. The second argument is a function that gets called every single time we visit a neighbor of the node.

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

We will keep a note of all the nodes that we need to visit by using the `queueCreator` function. The traversal of the algorithm will only work `while` the queue still has items in it. We will fill the queue with the `startingNode` and all of it’s neighbors.

Each time the `while` loop finishes an iteration, we remove a node from the queue and set it as the `currentNode`. If the algorithm is on a node that it has not previously visited, then we call the `neighborVisit` function and set it’s value to true.

Now take a look at the code below:

``````breadthFirst(startingNode, neighborVisit) {
const firstNode = this.searchNode(startingNode)
const visitedNode = nodes.reduce((sum, node) => {
sum[node.id] = false
return sum
}, {})
const queue = queueCreator()
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]) {
}
})
}
}  ``````

Let’s test the algorithm by creating a graph data structure:

``````const graph = graphCreator(true)

It should return a graph like this:

We use the `breathFirst` method to print the node ids.

``````graph.breadthFirst('c', node => {
console.log(node.id)
})
// Output
c
d
e
f``````

The algorithm starts with node `c` in this example. It is connected to nodes `d` and `e`. It will print out the nodes `c` followed by `d` and `e`. Next, the algorithm looks at the neighbors of `d` and discovers it is only connected to `e` which is ignored since it was already visited. That means it will next look at the neighbors of `e`. It’s only connected to node `f`, though. The algorithm will print that out in the console.

## Depth First Searching Algorithm

The Depth First algorithm is a traversal algorithm that starts searching at one node, then goes down the path of it’s neighboring nodes before it goes to the other paths.

Let’s take a look at the `graphCreator`object and create a new method named `depthFirst`. It’s similar, but not the same as `breadthFirst`. While it does take two arguments, one is used to define which node to start the traversal from and the other is a function that will be called when 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 a Depth First algorithm, if there is another level to go down, then the algorithm travels down that path first. We’ll create a function named `travel` that will check if the node in that path was already visited. If that returns true, then the algorithm will return nothing. Otherwise, the algorithm will call `neighborVisit` and mark the node as visited by setting the `sum[node.id]` value to true.

We loop through all the neighbors of the node and call `travel` on each of them. We 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)``````

Guess what??? The algorithm is ready! Let’s test it out on the graph that we used before.

``````const graph = graphCreator(true)

Calling `depthFirst` on the graph with `a` as the `startingNode` will provide us the following output:

``````graph.depthFirst('a', node => {
console.log(node.id)
})
// Output
a
c
d
e
f``````

Node `a` is first connected to node `c`. That means that the algorithm will travel down this path first. Node `c` is connected to node `d`, which is connected to node `e`, and finally `e` is connected to `f`.

## Binary Tree Traversal Algorithms

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

First, we create a function that will create a node that will take an `id` as an argument. It also has `left` and `right` properties that are both initially set to `null`. We will also write methods to add child nodes, one on the left path, one on the right path.

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

Now we get to the traversal part. A binary tree can be traversed in three separate ways:

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

The three of these seem quite similar, don’t they? Each will receive a starting node and a recurring function that the algorithm uses to traverse through the binary tree. Let’s create an object that will store the code for these traversal processes, shall we?

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

The `in-order` traversal algorithm first travels down the left branch, then continues to the current node, and finally down the right branch. Coding this algorithm is rather simple, and we use the `in` function as follows:

``````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 down the left path, and finally 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 algorithms 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. In 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`

## Conclusion

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.