Depth First Search

Pré-requisitos: Trees & Recursão.

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.

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

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?!".

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 é:

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.

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

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.

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.

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.

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.

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.

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

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.

Vamos escrever isso em código agora.

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.

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.

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.

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.

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.

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.

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.

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.

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

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