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

<img src="https://917734093-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F3cZYot05lrDVVoPkSu2L%2Fuploads%2F5SMKcJcaeecbrzfAM1zM%2Ffile.excalidraw.svg?alt=media&#x26;token=7bcebe29-00d0-4e53-95b5-562613f84b43" alt="" class="gitbook-drawing">

#### In more detail

{% hint style="warning" %}
In **Graphs**, you must also **mark visited nodes**, so that they don't get pushed again to the `Stack`.
{% endhint %}

{% hint style="success" %}
In `BST` where you garantee order, you may add additional conditions to prioritize going left or right first, depending on the `needle` value.
{% endhint %}

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.

```typescript
// 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;
}
```

```typescript
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);
}
```