BFS, DFS tree-traversing (7 min recap)

Motivation

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

DFS - stays for depth-first-search while BFS 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 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 - in case of BFS we shall use Queue and DFS implementation can benefit from Stack

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

    // 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

    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

    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

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

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

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

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

Stack

    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)