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)

Blog

BFS, DFS tree-traversing (7 min recap)

Yigal Ziskand

Motivation

Basic Idea

Pseudo Code

Abstract Search Approach

Code Snippet

BFS

DFS

Queue

Stack

Notes

Example

Join Our Newsletter. No Spam, Only the good stuff.

Related