Depth First Search (DFS)

About

Is a Graph or Tree traversal algorithm used to explore nodes and edges. It can also be used as a Search algorithm.

Preserves the shape of the traversal.

It uses Stack to store nodes in order.

How it Works

DFS explores entire branches (goes all the way to the leafs) first before moving to neighbor branches.

In more detail

In Graphs, you must also mark visited nodes, so that they don't get pushed again to the Stack.

In BST where you garantee order, you may add additional conditions to prioritize going left or right first, depending on the needle value.

1. At start node N:

   1. Push N to the Stack.

   2. Push N's children to the Stack.

   3. Process N and remove it from the Stack.

2. Pop next node N (last) from Stack:

   1. Push its children to the Stack.

   2. Process node N, and remove it from Stack.

3. Repeat 2. until all nodes were processed.

// Considering a Binary Tree
function dfs(head: BinaryNode<T>, needle: T): boolean {
    const stack = [head];
    
    while (stack.length) {
        const node = stack.pop();
        // Needle found
        if (node.value === needle) return true;
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return false;
}

function dfsRecursive(curr: BinaryNode<T>, needle: T): boolean {
    if (!curr) return false;
    if (curr.value === needle) return true;
    return dfsRecursive(curr.left, needle) || dfsRecursive(curr.right, needle);
}