BFS, DFS tree-traversing (7 min recap)
Tags: algorithms, javascript, search
Published: 2021-05-25 12:25:58

---
title: BFS, DFS tree-traversing (7 min recap)
published: true
description: 7 min to memorize the concept
tags: #algorithm #js #search
---

## Motivation

> Let's begin our recap with understanding algorithm's names first.

> [DFS](https://en.wikipedia.org/wiki/Depth-first_search) \- stays for **depth-first-search** while [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) means **breadth-first-search**.

> If you pay close attention to the names you will see that both of them ends up with *SEARCH* term.
> Yes, you guess right - we can use both of them in order to perform search on [*tree structured*](https://en.wikipedia.org/wiki/Tree_%28data_structure%29) data-sets.

## Basic Idea

> The basic idea applied in **DFS** is to reach the deepest node in the graph whenever possible while **BFS** prioritizes wide-level node visiting approach.

> In other words **DFS** will perform iterations in \[TOP -> BOTTOM\] order while **BFS** will iterate in side-to-side approach \[LEFT -> RIGHT\] or \[RIGHT -> LEFT\].
> Due to their different approaches on iteration order - both of them utilize different [data-structures](https://en.wikipedia.org/wiki/List_of_data_structures) \- in case of **BFS** we shall use [Queue](https://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29 "https://en.wikipedia.org/wiki/Queue_(abstract_data_type)") and **DFS** implementation can benefit from [Stack](https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29 "https://en.wikipedia.org/wiki/Stack_(abstract_data_type)")

Two words on Queue & Stack that i think important for further reading.

- Queue is an abstract data type and its purpose is to store data in **FIFO** (*first in - first out*) order.
- Stack is an abstract data type as well that stores data in **LIFO** (*last in - first out*) order.

> We will implement our BFS & DFS example on [binary tree](https://en.wikipedia.org/wiki/Binary_tree) which is a valid data structure with the only difference (*from our perspective*) \- any tree's node can have at most two children nodes.

## Pseudo Code

### Abstract Search Approach

```js
    // initial step - storing root node
    collection = collection.putItem(tree_root)

    // initialize iteration loop
    do:
        node = collection.getItem()
        if node has children:
            collection.storeChildren(node.children)
    // termination condition
    while collection not empty

```

## Code Snippet

### BFS

```js
    const BFS = async ({ root }, collection) => {
        if (!root) {
            return;
        }        

        const queue = new Queue();
        let node;

        queue.enqueue(root);

        while (queue.size() > 0) {
            node = queue.dequeue();

            if (node.l_child) {
                queue.enqueue(node.l_child);
            }

            if (node.r_child) {
                queue.enqueue(node.r_child);
            }

            // This line should be replaces by any logical operation you want to perform on the node's value, ex: sum
            // In my particular example i use Svelte's store (kind of observer pattern) to collect node's value
            await collection.update(collectedData => collectedData = [...collectedData, node.value]);
        }
    }
```

### DFS

```js
    const DFS = async ({ root }, collection) => {
        if (!root) {
            return;
        }

        const stack = new Stack();
        let node;

        stack.push(root);

        while (stack.size() > 0) {
            node = stack.pop();

            if (node.l_child) {
                stack.push(node.l_child);
            }

            if (node.r_child) {
                stack.push(node.r_child);
            }

            // the same explanation as for BFS (above)
            await collection.update(collectedData => collectedData = [...collectedData, node.value]);
        }
    }
```

### Queue

```js
    class Queue {
        constructor() {
            this.items = new Array();
        }

        enqueue(item) {
            this.items.unshift(item);
        }

        dequeue() {
            return this.items.pop();
        }

        size() {
            return this.items.length;
        }
    }
```

### Stack

```js
    class Stack {
        constructor() {
            this.items = new Array();
        }

        push(item) {
            this.items.push(item);
        }

        pop() {
            return this.items.pop();
        }

        size() {
            return this.items.length;
        }
    }
```

> Technically we did not have to implement neither Stack nor Queue for BFS, DFS search - we could just use regular Array and be happy with it... but i believe that by implementing Queue, Stack interface we can enjoy more readable code at the end.

## Notes

- Both of the algorithms will perform equally in big `O` perspective and in worst case it will be equal to `O(n)` \- meaning that all nodes of the data-set were visited.
- In case we have some knowledge regarding our data-set - we can benefit better results from each:
    - If required data is stored in a deep *(far from the root)* node - then DFS would give better results.
    - Looking for the shortest path between nodes will perform better with BFS.
- In average comparison DFS will consume less memory then BFS.

## Example

> As always i have sketched some clickable example with all the snippets from above.
> [Tree Traversing (*Svelte REPL*)](https://svelte.dev/repl/9380b95c75a34f9fa97cd17cf5214f73?version=3.38.2)