DFS

Depth-First Search (DFS) is a traversal algorithm that starts at a specified node and explores as far as possible along each branch before backtracking.

It uses a stack data structure to keep track of the nodes to be visited next.

pseudocode:

DFS(graph, start_node):
    // Initialize a stack for DFS traversal and a set to keep track of visited nodes
    stack = [start_node]
    visited = set()

    // While there are still nodes to explore
    while stack is not empty:
        // Pop the top node from the stack
        current_node = stack.pop()

        // If the current node has not been visited
        if current_node not in visited:
            // Mark the current node as visited
            add current_node to visited

            // Process the current node (optional)

            // Explore all adjacent nodes of the current node
            for each neighbor of current_node:
                // If the neighbor has not been visited, push it onto the stack
                if neighbor not in visited:
                    stack.push(neighbor)

The steps involved in the DFS algorithm are as follows:

Start at a specified node.
Push the node to a stack and mark it as visited.
While the stack is not empty:
1. Pop a node from the top of the stack.
2. Visit the node and perform some operation on it.
3. Push all the neighboring nodes that have not been visited before to the stack and mark them as visited.
Repeat step 3 until the queue is empty.

DFS explores all the nodes in a branch before backtracking to explore other branches. This makes it useful for exploring all the nodes in a graph and for detecting cycles in a graph. DFS can also be used to find a path between two nodes in a graph.

There are three types of DFS traversal:

In-Order
Pre-Order
Post-Order

In-Order traversal visits the left subtree, then the current node, and then the right subtree.

Pre-Order traversal visits the current node, then the left subtree, and then the right subtree.

Post-Order traversal visits the left subtree, then the right subtree, and then the current node.

The time complexity of DFS is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

The space complexity of DFS is O(V), as it needs to keep track of all the visited nodes and the nodes in the stack.

DFS is a useful algorithm for exploring all the nodes in a graph and for detecting cycles in a graph.

It can also be used to find a path between two nodes in a graph.

DFS Good at 😀:

Less Memory
Does Path Exist?

DFS Bad at 😒:

Can Get Slow

BFS vs. DFS

	BFS	DFS
Approach	Explores level by level	Explores branch by branch
Data Structure	Uses a queue	Uses a stack or recursion
Memory Usage	Requires more memory	Requires less memory
Time Complexity	O(V+E)	O(V+E)
Use Cases	Shortest path in unweighted graph, reachable nodes from a starting node	Detecting cycles, exploring all nodes in a graph

BFS

DFS

Approach

Explores level by level

Explores branch by branch

Data Structure

Uses a queue

Uses a stack or recursion

Memory Usage

Requires more memory

Requires less memory

Time Complexity

O(V+E)

Use Cases

Shortest path in unweighted graph, reachable nodes from a starting node

Detecting cycles, exploring all nodes in a graph

Note that while BFS and DFS have their own strengths and weaknesses, the actual performance of the algorithms may depend on the structure and size of the graph being traversed.

DFS will iterate through our data structure in a "vertical way". Following the same example we used for BFS, the values would be traversed in the following order: [10, 6, 3, 8, 15, 20].

This way of doing DFS is called "pre order". And there're actually three main ways in which DFS can be done, each being different by just changing the order in which nodes are visited.

Pre order: Visit current node, then left node, then right node.
Post order: Explore all children to the left, and all children to the right before visiting the node.
In order: Explore all children to the left, visit the current node, and explore all children to the right.

If this sounds confusing, don't worry. It's not that complex and it will become clearer in short with a few examples.

Pre order DFS

In a pre order DFS algorithm we do the following:

Create a variable to store the values of the visited nodes
Store the root of the tree in a variable
Write a helper function that accepts a node as a parameter
Push the value of the node to the variable that stores values
If the node has a left property, call helper function with left node as parameter
If the node has a right property, call helper function with left node as parameter

pseudocode:

procedure preOrderDFS(node)
    if node is null
        return
    visit(node) // Visit the current node
    preOrderDFS(node.left) // Recursively visit the left subtree
    preOrderDFS(node.right) // Recursively visit the right subtree

A possible implementation could be the following:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }

}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSPreOrder()) // [ 10, 6, 3, 8, 15, 20 ]

Post order DFS

In post order DFS algorithm we do the following:

Create a variable to store the values of the visited nodes
Store the root of the tree in a variable
Write a helper function that accepts a node as parameter
If the node has a left property, call helper function with left node as parameter
If the node has a right property, call helper function with left node as parameter
Call the helper function with the current node as parameter

pseudocode:

post_order_dfs(node):
    if node is not null:
        // Visit left subtree
        post_order_dfs(node.left)
        
        // Visit right subtree
        post_order_dfs(node.right)
        
        // Visit current node
        visit(node)

A possible implementation could be the following:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }


    DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSPostOrder()) // [ 3, 8, 6, 20, 15, 10 ]

In order DFS

In in order DFS algorithm we do the following:

Create a variable to store the values of the visited nodes
Store the root of the tree in a variable
Write a helper function that accepts a node as parameter
If the node has a left property, call helper function with left node as parameter
Push the value of the node to the variable that stores values
If the node has a right property, call helper function with left node as parameter
Call the helper function with the current node as parameter

pseudocode:

function inOrderDFS(node):
    if node is not null:
        // Traverse left subtree
        inOrderDFS(node.left)
        
        // Visit current node
        visit(node)
        
        // Traverse right subtree
        inOrderDFS(node.right)

A possible implementation could be the following:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    DFSInOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSInOrder()) // [ 3, 6, 8, 10, 15, 20 ]

As you probably noticed, pre order, post order, and in order implementations are all very similar and we just change the order of how nodes are visited.

The traversal result we get to is quite different with each implementation and sometimes one might come in handy more than others.

Regarding when to use BFS or DFS, as I said it depends on how our data structure is organized.

Generally speaking, if we have a very wide tree or graph (meaning there are lots of sibling nodes that stand on the same level), we should prioritize DFS.

And if we're dealing with a very large tree or graph that has very long branches, we should prioritize BFS.

The time complexity of both algorithms is the same, as we're always visiting each node just once.

But space complexity can be different depending on how many nodes have to be stored in memory for each implementation.

So the fewer nodes we have to keep track of, the better.

PreviousBFS NextDijkstra

Last updated 7 months ago