Lowest Common Ancestor

O Lowest Common Ancestor (LCA) é um problema clássico de árvores cujo objetivo é encontrar o ancestral comum mais profundo entre dois nós.

---

Definição

Dado dois nós p e q em uma árvore, o Lowest Common Ancestor é o nó mais profundo que é ancestral de ambos.

Um nó pode ser ancestral de si mesmo.

---

Exemplo

Em uma árvore binária:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

• LCA(5, 1) = 3
• LCA(5, 4) = 5
• LCA(6, 4) = 5

---

Principais variações do problema

1. Árvore binária genérica (sem propriedades extras)
2. Binary Search Tree (BST)
3. Múltiplas consultas de LCA (pré-processamento)
4. Árvore com ponteiro para o pai

Cada variação admite soluções diferentes.

---

Caso 1 — Árvore binária genérica (solução clássica DFS)

Ideia

• Percorra a árvore recursivamente
• Se o nó atual for None, retorne None
• Se o nó atual for p ou q, retorne ele
• Procure nos dois lados:
  • Se ambos retornarem não nulo, o nó atual é o LCA
  • Caso contrário, retorne o lado não nulo

Implementação (Python)

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
 
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
 
    if left and right:
        return root
    return left or right

Complexidade

• Tempo: O(n)
• Espaço: O(h) (stack da recursão)

---

Caso 2 — Binary Search Tree (BST)

Propriedade usada

Em uma BST:

• Valores à esquerda são menores
• Valores à direita são maiores

Ideia

• Se p e q forem menores que o nó atual → vá para a esquerda
• Se forem maiores → vá para a direita
• Caso contrário → nó atual é o LCA

Implementação

def lowestCommonAncestor(root, p, q):
    cur = root
    while cur:
        if p.val < cur.val and q.val < cur.val:
            cur = cur.left
        elif p.val > cur.val and q.val > cur.val:
            cur = cur.right
        else:
            return cur

Complexidade

• Tempo: O(h)
• Espaço: O(1)

---

Caso 3 — Árvore com ponteiro para o pai

Ideia

• Suba de p até a raiz, marcando ancestrais
• Suba de q até encontrar um ancestral marcado

Complexidade

• Tempo: O(h)
• Espaço: O(h)

---

Caso 4 — Muitas consultas de LCA (avançado)

Usado quando há milhares ou milhões de consultas.

Técnicas comuns

• Binary Lifting
• Euler Tour + RMQ
• Tarjan Offline LCA

Binary Lifting (resumo)

• Pré-processamento O(n log n)
• Cada consulta em O(log n)
• Usado em programação competitiva e sistemas de grafos

---

Intuição importante

• O LCA é o ponto onde os caminhos até p e q se encontram
• Na solução DFS, o retorno não nulo “propaga” a informação de onde os nós foram encontrados

---

Armadilhas comuns

• Esquecer que um nó pode ser ancestral dele mesmo
• Assumir que a árvore é BST quando não é
• Retornar o primeiro ancestral comum, não o mais profundo

---

Padrões algorítmicos envolvidos

• DFS / Recursão
• Divisão de subproblemas
• Propriedades estruturais da árvore
• Pré-processamento para queries rápidas

---

Contexto de entrevistas

O LCA testa:

• Entendimento profundo de árvores
• Capacidade de adaptar a solução ao contexto
• Clareza na análise de complexidade