BFS VS DFS

Back at again with the data structure and algorithm journal. In the last journal of the data structure, we talk about binary search trees. In this article, we are going to dive into how we traversal a tree. Not necessarily a binary search tree, it could be a binary tree that’s unsorted or a ternary tree or just any other tree that has no particular order.

Let’s contrast it with a linked list to traverse a tree for every node one time. In the linked list, we only have one linear pathway from head to tail when traveling a singly linked list, no order whatsoever to decide. With a tree data structure, it is very different. There are a lot of ways to visit every node at once. It is not like a linked list, just one linear approach. There are two main known approaches in traversing a tree.

BFS is going to horizontally the same level first while DFS is going to vertically first.

Breadth-first Search

Breadth-first search (BFS) is working across the tree first. Traverse the same level (breadth) of the tree before moving down. We want to visit every node on the same level first.

BFS is going over the same level first (left-right horizontally)

Implementation BFS

Imagine we have a tree-like the above picture.

• First, we create a queue(usually an array) and a variable to store the values of nodes visited.
• Place the root node in the queue.
• Loop as long as there is anything in the queue.
• Dequeue a node from the queue, push the node’s value into the variable that stores the nodes.
• If there is a left property on the node dequeued- add it to the queue.
• If there is a right property on the node dequeued -add it to the queue.
• Return the variable that stores the values.

As a result, the data will first place the same level (horizontal before going to vertical, breath before depth). It is the same principle with a queue data structure(First In First Out -FIFO) when it comes to the implementation of BFS.

BFS implementation

Depth-first Search

There are three different orders within the depth-first search(DFS); preorder, postorder, and Inorder. All of them traverse nodes vertically, down to the end of the tree before visiting sibling nodes. The only difference is in traversing the tree; other than that, they all travel vertically rather than horizontally(BFS). Spoiler alert: the difference between these three orders is within one or two lines of code shift. There will also be recursion since it is a lot easier and a shorter line of code than iteratively. (note I will not explain recursion here; that will be another topic-but before diving deeper into DFS; I recommend you to understand recursion first) .

DFS is going over depth-first (Top-down vertically).

Three types of DFS orders

• Pre-order: the node is processed first, then the left sub-branch, and then its right sub-branch last. For instance, the outcome above picture with pre-order would be [10,6,3,8,15,20].
• Post-order: left sub-branch of the nodes is processed first, then the right sub-branch, and then the node itself. The root node would be the last node to input; the children would go over first, then the root is the last to input. For instance, in the above picture, the outcome of the post-order data would be [3,8,6,20,15,10].
• In-Order: left sub-branch of the node are processed first, then the node itself, and then its right sub-branch last. For instance, the outcome with the above picture with in-order data would be [3,6,8,10,15,20].

Difference between DFS (3 types of orders ) and BFS

Implementation DFS

Implementation for all 3 DFS orders is similar; only the steps are different.

Pre-order

pre-order implementation

If there is a node in the property left, we will recursively call the helper function with the node’s left property. Once we finish the left, the same thing goes to the right. If the node has the right property, we will recursively call the helper function with the node’s right property. Lastly, invoke the helper function with the current variable.

Post-order

post-order implementation

Nearly is the same as a preorder; the only difference is visiting the left and right branches first. Lastly, visiting the root itself, as you can see, the codes are the same, but the orders are different.

In-order

In-order implementation

Again, it is the same with preorder and postorder. The only difference is visiting the left branch first, the root node itself next, and the right branch.

When to use BFS and DFS?

It depends on the tree; if the tree structure is spread out (wider), DFS should be more efficient in space complexity. The time complexity for DFS and BFS should be the same. With DFS, we only have to keep track of the nodes in a given branch down to the end with recursion. Instead, BFS is storing every node across the tree, and it will take more space. On the other hand, if the tree structure is deep, DFS could take more space.

So there you go, we finished with the tree data structures concepts. I hope you find the article is helpful and enjoyable. See you at the next data structure journals.

Reference:

https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/