Breadth-first vs Depth-first Tree Traversal in Javascript

When we search through a tree to find if it contains a certain node, there are two algorithms we can build. We can traverse the tree with a breadth-first or depth-first approach.

The depth-first method believes in going as far down the tree as possible until it reaches a dead end. Once it hits a null value, it starts back up at the top and follows the same process.

The breadth-first method tries its best to stay as close to the top as possible. It traverses the tree one row at a time and looks at all of its the sibling nodes. It continues this until it reaches the last row.

Building a simple Node and Tree class

The Node class will have a constructor with two properties. It will have a data property to store the value of the node and a children property to hold an array of child nodes. The add() method can be used to add new nodes to the Tree and the remove() method will delete an unwanted child node.

When building a Tree class, we only need a property to point to the first node, also known as the root.

Inside of the Tree class is where we build our DFS and BFS search functions to search through a Tree of nodes.

Depth-First Algorithm

To check to see a tree contains a certain value using the DFS approach, we will create a function that starts off by declaring the collections array, which will contain the root node. We will then build a while loop that will run until there is no longer a value inside of the array.

The DFS uses a Stack to traverse down the tree of nodes. We will declare the current node by shifting off the first value of the array. With this node, we will check to see if its data is equal to the value we are searching for. If its equal, we will return True and exit out of the function. If the node’s value does not match, we will push the children of that node to the front of the array if they exists. We unshift the children to the front because the DFS approach wants us to go all the way to the bottom of the tree before checking any sibling element. If no value matches after searching the whole tree, we return false at the end of our function.

Breadth-First Algorithm

After building the DFS function, the BFS function will look very similar, but with one small difference. When we use the BFS approach, we want to check all sibling elements before going to the next row of the tree. We will accomplish this by using a Queue. The Queue requires us to use the push method instead of the unshift method when handling the children of the node. Instead of taking the children of a node and setting them into the front of the collections array, we will instead push them to the end. This makes sure that we will check all sibling elements before going to the next row of the tree.

When to use BFS vs. DFS?

Both algorithms can come in handy when traversing through a tree to look for a value, but which one is better? It all depends on the structure of the tree and what you are looking for. If you know the value that you are looking for is closer to the top, a BFS approach might be a superior choice, but if a tree is very wide and not too deep, a DFS approach might be faster and more efficient. Just keep in mind that there are many other factors that you will need to determine before choosing which approach to take. I have confidence you will figure it out!