Home Programming Learn Javascript Algorithms: Graph and Tree Traversal

Learn Javascript Algorithms: Graph and Tree Traversal

0
Learn Javascript Algorithms: Graph and Tree Traversal
<a href="https://www.pexels.com/photo/background-beautiful-blossom-calm-waters-268533/" target="_blank" rel="noopener noreferrer">Pixabay</a> at Pexels

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 Searching Algorithm

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 {
    add(x) {
      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,
    addNeighbors(node) {
      neighbors.push(node)
    }
  }
}

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

      a.addNeighbors(b)
      if (!uni) {
        b.addNeighbors(a)
      }
      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 graphCreatorobject we create a breadthFirst method. That method will take two arguments as params. The first argument will be the idof 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()
  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)
      }
    })
  }
}  

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

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')

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 graphCreatorobject 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)
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 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,
    addToLeft(leftId) {
      const newLeftNode = nodeCreator(leftId)
      this.left = newLeftNode
      return newLeft
    },
    addToRight(rightId) {
      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-orderalgorithm 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())
// output
h => 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'))
// output
a => 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'))
// output
h => 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.