Traversing Trees: Breadth First and Depth First Searches with JavaScript
When I was younger, I used to have files and folders randomly strewn about on my desktop and external hard drives. As I reached high school where most of my work was done on a computer, I realized that it was really difficult to find anything on my laptop since the file organization was haywire.
It took a full weekend to completely re-organize all of my files — this was before USB 3.0 came out. Other than a few hectic times in college, my files and folders stayed pretty clean, and it helped when cloud storage started to take over.
Trees
Files and folders on computers are organized in data structures called trees. Trees are a hierarchical collection of nodes that follow some simple rules:
- A tree has one node, the root, from which all nodes stem, either directly or as a child of a descendant node (which also means no node can have a reference to the root)
- A node can only have one reference (no node can have multiple other nodes pointing at it)
I’ve previously covered a special kind of tree called a binary search tree, but in this blog we’ll be working with a basic implementation of a tree — see below.
Breadth First Search
While our computer has a handy interface for browsing through our file tree, we need ways to programmatically traverse trees. One of these is called Breadth First Search. Breadth First Searches (referred to as BFS) traverse trees from left to right, then top to bottom, as if it were reading each row of nodes.
If we utilized BFS on the example above, we’d get this answer:
First Row: H + Second Row: el + Third Row: loWorld = HelloWorld
In order to do this programmatically we’ll need to use another data structure called a Queue. A Queue is a way of processing data that follows a First In First Out mentality. New data gets added to the back of the queue, and data gets processed from the front of the queue. Here’s my implementation:
When we process a node from the front of the queue, we’ll check if the node has any children, and if it does, add them to the back of the queue. We’ll also need to keep track of each node’s value by adding it to an array. Here’s my implementation:
If you want to see the code in action using the tree example I posted above, see the bottom of this post.
Depth First Search
Depth First Search (referred to as DFS) is an alternate way of traversing a tree that uses recursion. Using DFS we can traverse trees in different ways depending on the order that we need. In each of the implementations, I’ll be referring to this number tree:
We’ll also be writing a helper method for each order, and using a switch statement to stipulate the order we want to use. Here’s the outer function:
Pre-Order
Pre-Order traverses the tree vertically from top to bottom, left to right. The first value returned will always be the root. For the number tree above, we’d get a return of [10,6,3,8,7,15,20] .
We need to first push the current node’s value, and then recursively call the function on each child of the current node.
Post-Order
Post-Order is similar to Pre-Order except for one facet: it traverses the tree horizontally from bottom to top, left to right. The root should always be the last thing returned. The tree above would return [3,8,7,6,20,15,10] .
We simply reverse the order in which actions happen in our pre-order function. We recursively call the function before adding any nodes to our array.
In-Order
In-Order is a bit different from the other two orders. It tries to recreate some semblance of the tree structure. It does so by traversing the tree from bottom to top, left to right, similar to post-order. However, it splits the children of every node in two, processing first the left half, then the parent node, then the right half. Our example would return [3, 6, 8, 7, 10, 15, 20].
Since our there are no restrictions on the number of children each node can have, we need to split the nodes ourselves. In-order DFS is easily implemented with Binary Search Trees, where each node can only have a maximum of 2 children, and the left and right nodes are specifically defined. In fact, because of the way Binary Search Trees are sorted, when DFS is used on a binary search tree it returns a sorted array of all node values.
When to use BFS and DFS
BFS and DFS both have a time complexity of O(n) at worst. BFS is better for deeper trees since it will take a lot more memory to operate on wider trees. The opposite applies to DFS — it will take a lot of memory to traverse deeper trees while it works well with wider trees. Since they are both meant for searching, you also need to consider what results you are searching for. Take a look at the stack overflow I’ve linked in the resources section for further explanation.
