---
description: 'Pré-requisitos: Trees & Recursão.'
---

# Depth First Search

DFS, como o nome indica, é uma busca ousada. Nós vamos o quão fundo nós podemos para encontrar um valor, e, caso não encontremos, nós refazemos nossos passos e procuramos em outro lugar. DFS é basicamente uma pre-order traversal de uma árvore.&#x20;

Vamos olhar um problema simples. Procure um node em uma árvore binária que tenha um valor igual a target.

```python
def dfs(root, target):
    if root is None:
        return None
    if root.val == target:
        return root
    
    left = dfs(root.left, target)
    if left is not None:
        return left

    return dfs(root.right, target)
```



### DFS Template

A chave para resolver problemas DFS é pensando "Se eu fosse um nó, o que eu faria?!".&#x20;

Um node só sabe de duas coisas: seu valor, e como chegar em seus filhos. Nesse caso, você precisa criar um algoritmo que trabalhe com essas duas informações e deixar a recursão tomar conta do resto.

O template para DFS é:

```python
def dfs(node, state):
    if node is None:
        # ...
        return
    
    left = dfs(node.left, state)
    right = dfs(node.right, state)
    
    # ...
    
    return # ...
```



### Definindo a Função Recursiva

Há duas coisas que precisamos para definir a função recursiva:

1. **O valor de retorno (passar o valor dos filhos para os pais)**\
   O que nós queremos retornar após checar um node? Por exemplo, no caso de achar um node, nós queríamos retornar o node com o valor desejado, ou null caso não encontrássemos. Use o valor de retorno para passar informações dos filhos para os pais.
2. **Identificar estados (passar valor dos pais para os filhos)**\
   Qual valor nós precisamos manter guardado para termos as informações necessárias para progredirmos na resposta? Por exemplo, caso queiramos descobrir se um node tem valor maior que o de seu pai, nós precisamos manter o valor do pai como um estado. Esses estados viram os argumentos da função. Use estados para passar informações dos pais para os filhos.



### Maior Depth de uma Tree

Dado uma árvore binária, encontre sua maior profundidade.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FKnU9eD4wcaUSBiGHgw6h%2Ftree_max_depth.png?alt=media&#x26;token=b0af6dcb-1fa4-4a09-95fb-cbcc251785dd" alt=""><figcaption></figcaption></figure>

A resposta no exemplo acima é 2. Lembre-se que a profundidade (depth) é determinada pela quantidade de arestas (edges), e não pela quantidade de nós (nodes).&#x20;

Vamos pensar primeiramente no valor de retorno, o que nós queremos retornar quando checarmos um node? Dado que nós queremos saber a profundidade máxima da árvore, seria bastante apropriado retornar a profundidade da subárvore em que aquele node se encontra. Quanto ao estado, nós não precisamos saber mais nada do que a profundidade da atual subárvore, uma vez que nós podemos passar esses valores para os pais usando a recursão, e ir somando até encontrarmos a profundidade máxima.&#x20;

Agora, como sabemos a profundidade? Lembre-se que depth é igual ao número de edges, e o número de edges pode ser calculado como o número de nodes em uma sequência - 1. Vamos então criar uma função recursiva que detecta a maior sequência de nodes, e então subtrair 1 para descobrirmos a maior depth da tree.&#x20;

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2Fm8R1JipTGzPWYTjXmx7y%2FScreenshot%202024-12-01%20at%2012.41.45.png?alt=media&#x26;token=39f7e16f-d047-458f-a399-31e2b95ec51f" alt=""><figcaption></figcaption></figure>

Por exemplo, imagine que nós chegamos no node de valor 3 na árvore, e nós vamos tratar ele como uma subárvore, portanto, ele tem uma profundidade 0, e possui 1 node, iremos retornar 1, e então iremos somar isso até chegarmos na root e encontrarmos o valor 3, pois é a maior sequência de nodes em um caminho, e então basta subtrair 1 para revelarmos que a árvore acima possui profundidade máxima de 2. Vejamos isso em código agora.

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def tree_max_depth(root: Node) -> int:
    def dfs(root):
        if root is None:
            return 0
        
        left = dfs(root.left)
        right = dfs(root.right)
        return max(left, right) + 1
    
    return dfs(root) - 1 if root else 0
```

Perceba que quando a root é nula, ou seja, chegamos no final da árvore, nós retornamos 0 pois não tem nenhum node lá, então somamos 1 pois tem um node com 2 pointeiros vazios, e aí vamos repetindo isso e fazendo somas até encontrar a maior sequência de nodes.

Caso não consiga visualizar isso ainda, pegue um papel e caneta e desenhe a **call stack**, analise com atenção até você conseguir visualizá-la, é importante ser capaz de visualizar a call stack caso você realmente queira entender recursão e DFS.&#x20;



### Nodes Visíveis em uma Binary Tree

Em uma árvore binária, um node é dito visível se no caminho do node para a root não tem nenhum node com valor maior que o dele.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FslTnZQgDvR8x9VNbO79z%2Fvisible_tree_node.png?alt=media&#x26;token=bf1e9933-162c-46fb-8f03-b4531631f270" alt=""><figcaption></figcaption></figure>

Vamos pensar no nosso template, para isso, tem duas perguntas que temos de responder:&#x20;

a. qual valor nós queremos retornar?

_r:_ Nós queremos retornar quantos nodes visíveis encontramos em cada subárvore, e é só deixar a recursão fazer o trabalho de ir somando esses nodes até chegarmos na resposta final.

b. qual estado queremos passar dos pais para os filhos?

_r:_ Como a condição para um node ser visível é não ter nenhum node **maior** que ele no caminho dele para a root, podemos passar o maior valor encontrado até o momento naquele caminho para os filhos.&#x20;

Vamos escrever isso em código agora.

```python
from math import inf

def visible_tree_node(root: Node) -> int:
    def dfs(root, max_so_far):  
        if root is None:
            return 0

        total = 0
        
        if root.val >= max_so_far:
            total += 1
        
        total += dfs(root.left, max(root.val, max_so_far))
        total += dfs(root.right, max(root.val, max_so_far))
        
        return total
        
    return dfs(root, -inf)
```



### Binary Search Tree

Uma Binary Search Tree é uma árvore onde cada node é maior que os nodes da subárvore à esquerda e menor do que os nodes da subárvore à direita.&#x20;

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FdJjx4TzK74bJmcM9CM0P%2Fbinary-search-tree-true-false.jpeg?alt=media&#x26;token=dc686982-713e-4b96-9531-312c6a3047bc" alt=""><figcaption></figcaption></figure>

**Searching.**

O propósito de uma binary search tree é para fazer buscas de forma eficiente. Você pode buscar um elemento em um curto período de tempo, como você faria em uma busca binária.&#x20;

Se um node é maior do que o valor que você está procurando, procure na subárvore à esquerda. Se é menor, procure na subárvore à direita. Se for igual, parabéns, você encontrou o item!

Uma busca em uma binary search tree tem uma complexidade de tempo de O(h), onde h é a altura da árvore. No melhor caso, a altura da árvore é proporcional ao log do tamanho da árvore.&#x20;



**Insertion.**

Uma das vantagens de utilizar uma BST em comparação com uma lista ordenada é que quando você acrescentar um novo valor a uma BST, outros valores não vão precisar se mover para adequar o novo valor.&#x20;

Ao invés disso, primeiro nós procuramos o item na BST. Se encontramos uma árvore vazia, substituímos ela com o novo node com o valor que desejamos.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FvtJyfJ8lM22dYGBShXFr%2Fbst_intro_insertion.png?alt=media&#x26;token=6855f754-7e06-4d2d-bf7c-ead59e22e3ac" alt=""><figcaption></figcaption></figure>

A complexidade de tempo para adicionar um item em uma BST também é O(h), onde h é a altura da árvore.



**Deletion.**

Deletar um node em uma BST é bem simples, primeiro, encontre o item que você deseja deletar.&#x20;

Após encontrar o item, se a subárvore direita estiver vazia, pegue o primeiro node da subárvore da esquerda e atribua ao node atual.&#x20;

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FY1Wgu1XjuAJBelkqdMRS%2Fd1%20(1).png?alt=media&#x26;token=58c5c26c-21a6-405e-92d5-3c91c08f3f09" alt=""><figcaption></figcaption></figure>

No caso acima, a subárvore direita está vazia. Então, o ponteiro para o node da subárvore esquerda é alocado para o node atual. Esse ponteiro naturalmente tem o valor nulo, pois a subárvore esquerda também está vazia.

Caso você queira deletar um node que a subárvore direita não está vazia, você vai precisar pegar o valor mais à esquerda da subárvore direita desse node e atribuir ao node que você está deletando.

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2F4Z840N168SslG2v2kJhS%2Fd3.png?alt=media&#x26;token=9f389893-7b52-4561-a2f3-e44cbb908778" alt=""><figcaption></figcaption></figure>

O motivo para ser o node mais à esquerda da subárvore direita é porque o node tem que ser maior que todos os elementos da subárvore da esquerda, e menor que todos os elementos da subárvore direita. O node mais à esquerda da subárvore direita satisfaz esses dois critérios, ele é maior que todos os elementos da subárvore esquerda e menor que todos os outros elementos da subárvore direita.



### Implementação de uma BST

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find(tree, val):
    if tree is None:
        return False
    if tree.val == val:
        return True
    elif tree.val < val:
        return find(tree.right, val)
    else:
        return find(tree.left, val)

def insert(tree, val):
    if tree is None:
        return Node(val)
    if tree.val < val:
        tree.right = insert(tree.right, val)
    elif tree.val > val:
        tree.left = insert(tree.left, val)
    return tree
```
