Tree Traversal — Como Percorrer Árvores

Tree Traversal (percurso em árvores) é o conjunto de técnicas utilizadas para visitar os nós de uma estrutura de dados chamada árvore.

Árvores aparecem em diversos lugares da computação:

• Estruturas de arquivos
• Bancos de dados
• Sistemas de busca
• DOM de páginas web
• Sistemas de decisão
• Compiladores
• Inteligência artificial
• Estruturas de índices
• Árvores binárias de busca

Para trabalhar com árvores, precisamos primeiro entender como percorrer todos os seus nós.

Os principais métodos são:

DFS
├── Preorder
├── Inorder
└── Postorder

BFS
└── Level Order

1. O que é uma árvore?

Uma Tree é uma estrutura de dados hierárquica formada por nós.

Imagine uma organização de arquivos:

Projeto
├── src
│   ├── components
│   └── pages
├── public
└── package.json

Isso é uma estrutura de árvore.

Temos um elemento inicial:

Projeto

Chamado de:

Root

E seus elementos filhos:

src
public
package.json

Dentro de src, temos outros elementos:

components
pages

Cada elemento pode ter seus próprios filhos.

2. Estrutura de uma árvore

Podemos representar uma árvore assim:

          A
        /   \
       B     C
      / \     \
     D   E     F

Temos:

A → Root

Os filhos de A são:

B e C

Os filhos de B são:

D e E

O filho de C é:

F

Os nós que não possuem filhos são chamados de:

Leaf Nodes

Nesse exemplo:

D
E
F

são folhas.

3. O que é uma árvore binária?

Uma Binary Tree (árvore binária) é uma árvore em que cada nó pode ter no máximo dois filhos.

Normalmente chamamos os filhos de:

Left
Right

Por exemplo:

        10
       /  \
      5    15
     / \     \
    3   7     20

O nó 10 possui:

Left  → 5
Right → 15

O nó 5 possui:

Left  → 3
Right → 7

Já o nó 3 não possui filhos.

Uma implementação simples seria:

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Podemos criar uma árvore:

const root = new TreeNode(10);

root.left = new TreeNode(5);
root.right = new TreeNode(15);

root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);

root.right.right = new TreeNode(20);

Visualmente:

        10
       /  \
      5    15
     / \     \
    3   7     20

4. O que é Tree Traversal?

Tree Traversal significa percorrer os nós de uma árvore seguindo uma determinada ordem.

Por exemplo:

        10
       /  \
      5    15
     / \     \
    3   7     20

Podemos visitar:

10 → 5 → 3 → 7 → 15 → 20

Ou:

3 → 5 → 7 → 10 → 15 → 20

Ou ainda:

3 → 7 → 5 → 20 → 15 → 10

A ordem depende do algoritmo utilizado.

5. DFS e BFS

Existem duas grandes categorias de Tree Traversal.

Tree Traversal
│
├── DFS
│
└── BFS

DFS significa:

Depth-First Search

Busca em profundidade.

A ideia é:

Ir o mais fundo possível antes de voltar.

BFS significa:

Breadth-First Search

Busca em largura.

A ideia é:

Visitar os nós por nível.

6. DFS — Depth-First Search

Imagine:

        10
       /  \
      5    15
     / \     \
    3   7     20

Com DFS, podemos começar no 10.

Depois ir para:

5

Depois:

3

Chegamos ao final daquele caminho.

Então voltamos:

5

E visitamos:

7

Depois voltamos para:

10

E seguimos para:

15

Depois:

20

O conceito é:

10
 ↓
5
 ↓
3
 ↓
volta
 ↓
7
 ↓
volta
 ↓
15
 ↓
20

DFS normalmente utiliza:

• Recursão
• Stack

7. Preorder Traversal

No Preorder, a ordem é:

Root
Left
Right

Ou:

Root → Left → Right

Para:

        10
       /  \
      5    15
     / \     \
    3   7     20

O percurso será:

10 → 5 → 3 → 7 → 15 → 20

Primeiro visitamos:

10

Depois percorremos a subárvore esquerda:

5 → 3 → 7

Depois a direita:

15 → 20

8. Implementando Preorder

function preorder(
  root: TreeNode | null
): number[] {
  if (root === null) {
    return [];
  }

  const result: number[] = [];

  function traverse(node: TreeNode | null) {
    if (node === null) {
      return;
    }

    result.push(node.value);

    traverse(node.left);

    traverse(node.right);
  }

  traverse(root);

  return result;
}

Resultado:

[10, 5, 3, 7, 15, 20]

A ordem é:

10
 ↓
5
 ↓
3
 ↓
7
 ↓
15
 ↓
20

9. Inorder Traversal

No Inorder, a ordem é:

Left
Root
Right

Ou:

Left → Root → Right

Na mesma árvore:

        10
       /  \
      5    15
     / \     \
    3   7     20

O resultado será:

3 → 5 → 7 → 10 → 15 → 20

Observe que os valores estão ordenados.

Isso acontece porque essa árvore é uma Binary Search Tree, ou BST.

10. Implementando Inorder

function inorder(
  root: TreeNode | null
): number[] {
  if (root === null) {
    return [];
  }

  const result: number[] = [];

  function traverse(node: TreeNode | null) {
    if (node === null) {
      return;
    }

    traverse(node.left);

    result.push(node.value);

    traverse(node.right);
  }

  traverse(root);

  return result;
}

Resultado:

[3, 5, 7, 10, 15, 20]

A ordem:

Left
  ↓
Root
  ↓
Right

11. Por que Inorder é importante?

Em uma Binary Search Tree, os valores menores ficam à esquerda e os maiores ficam à direita.

Por exemplo:

        10
       /  \
      5    15
     / \     \
    3   7     20

Ao fazer:

Left → Root → Right

obtemos:

3 → 5 → 7 → 10 → 15 → 20

Ou seja:

Array ordenado

Por isso, o Inorder Traversal é frequentemente utilizado para:

• Obter valores de uma BST em ordem crescente
• Validar estruturas de BST
• Encontrar valores em ordem
• Processar dados ordenados

12. Postorder Traversal

No Postorder, a ordem é:

Left
Right
Root

Ou:

Left → Right → Root

Para:

        10
       /  \
      5    15
     / \     \
    3   7     20

O resultado será:

3 → 7 → 5 → 20 → 15 → 10

Primeiro visitamos os filhos.

Só depois visitamos o pai.

13. Implementando Postorder

function postorder(
  root: TreeNode | null
): number[] {
  if (root === null) {
    return [];
  }

  const result: number[] = [];

  function traverse(node: TreeNode | null) {
    if (node === null) {
      return;
    }

    traverse(node.left);

    traverse(node.right);

    result.push(node.value);
  }

  traverse(root);

  return result;
}

Resultado:

[3, 7, 5, 20, 15, 10]

14. Por que Postorder é útil?

Postorder é especialmente útil quando precisamos processar os filhos antes do pai.

Um exemplo clássico é excluir uma árvore.

Imagine:

        A
       / \
      B   C

Não podemos remover A primeiro se ainda precisamos acessar:

B
C

Então fazemos:

B
C
A

Primeiro removemos os filhos.

Depois o pai.

Esse padrão aparece em:

• Exclusão de árvores
• Avaliação de expressões
• Processamento de dependências
• Cálculos recursivos
• Compiladores

15. Comparando DFS

Para:

        10
       /  \
      5    15
     / \     \
    3   7     20

Temos:

Preorder

Root → Left → Right

10 → 5 → 3 → 7 → 15 → 20

Inorder

Left → Root → Right

3 → 5 → 7 → 10 → 15 → 20

Postorder

Left → Right → Root

3 → 7 → 5 → 20 → 15 → 10

Uma maneira fácil de memorizar:

Preorder

ROOT aparece primeiro.


Inorder

ROOT aparece no meio.


Postorder

ROOT aparece por último.

16. BFS — Breadth-First Search

Agora vamos conhecer o BFS.

Em vez de ir até o final de um caminho, visitamos os nós por nível.

Temos:

        10
       /  \
      5    15
     / \     \
    3   7     20

Primeiro nível:

10

Segundo nível:

5 → 15

Terceiro nível:

3 → 7 → 20

Resultado:

10 → 5 → 15 → 3 → 7 → 20

Esse tipo de percurso é chamado de:

Level Order Traversal

17. Implementando BFS

Para BFS normalmente utilizamos uma fila:

Queue

A ideia:

function levelOrder(
  root: TreeNode | null
): number[] {
  if (root === null) {
    return [];
  }

  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;

    result.push(node.value);

    if (node.left) {
      queue.push(node.left);
    }

    if (node.right) {
      queue.push(node.right);
    }
  }

  return result;
}

Resultado:

[10, 5, 15, 3, 7, 20]

18. Como o BFS funciona?

Começamos:

Queue:

[10]

Retiramos 10.

Adicionamos:

5
15

Agora:

Queue:

[5, 15]

Retiramos 5.

Adicionamos:

3
7

Agora:

Queue:

[15, 3, 7]

Retiramos 15.

Adicionamos:

20

Agora:

Queue:

[3, 7, 20]

Visitamos:

3
7
20

Resultado final:

10 → 5 → 15 → 3 → 7 → 20

19. DFS vs BFS

Podemos visualizar:

DFS

        10
       ↓
       5
       ↓
       3
       ↓
       7
       ↓
       15
       ↓
       20

A ideia é:

Profundidade primeiro.

Já o BFS:

        10
         ↓
      5     15
       ↓   ↓
      3  7 20

A ideia é:

Nível por nível.

20. Quando usar DFS?

DFS é uma boa escolha quando precisamos:

• Explorar toda a árvore
• Procurar um caminho
• Resolver problemas recursivos
• Processar subárvores
• Calcular propriedades de nós
• Trabalhar com profundidade

Por exemplo:

Qual é a altura máxima da árvore?

Podemos explorar recursivamente cada subárvore.

function maxDepth(
  root: TreeNode | null
): number {
  if (root === null) {
    return 0;
  }

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  return (
    1 +
    Math.max(
      leftDepth,
      rightDepth
    )
  );
}

Para:

        10
       /  \
      5    15
     /       \
    3         20

A altura é:

3

21. Quando usar BFS?

BFS é especialmente interessante quando precisamos encontrar algo pelo menor número de níveis.

Por exemplo:

Qual é a distância mínima entre a raiz e um determinado nó?

Ou:

Qual é o nó mais próximo que satisfaz determinada condição?

Como o BFS visita:

Nível 0
Nível 1
Nível 2
Nível 3

o primeiro momento em que encontramos um nó pode representar o menor número de passos em determinadas estruturas.

22. Exemplo prático: sistema de arquivos

Imagine:

Projeto
├── src
│   ├── components
│   │   └── Button.tsx
│   └── pages
│       └── Home.tsx
├── public
│   └── logo.png
└── package.json

Essa estrutura pode ser representada como uma árvore.

Podemos usar DFS para procurar um arquivo:

Projeto
 ↓
src
 ↓
components
 ↓
Button.tsx

Ou BFS para encontrar arquivos mais próximos da raiz:

Projeto
 ↓
src
public
package.json
 ↓
components
pages
logo.png

A escolha depende do problema.

23. Exemplo prático: DOM

O HTML de uma página também possui uma estrutura hierárquica.

Por exemplo:

<body>
  <main>
    <h1>Meu Site</h1>

    <div>
      <p>Hello World</p>
    </div>
  </main>
</body>

Podemos visualizar:

body
└── main
    ├── h1
    └── div
        └── p

Isso é uma árvore.

Um algoritmo de DFS poderia visitar:

body
main
h1
div
p

Isso é semelhante ao conceito utilizado quando navegamos pelo DOM.

24. Complexidade

Em todos os principais tipos de Tree Traversal, normalmente visitamos cada nó uma vez.

Se a árvore possui:

n

nós:

Time Complexity: O(n)

A complexidade espacial depende do algoritmo e da estrutura da árvore.

Para DFS recursivo:

Space: O(h)

onde h é a altura da árvore.

Para BFS:

Space: O(w)

onde w é a largura máxima de um nível.

Em uma árvore muito desbalanceada, DFS pode ter:

O(n)

de espaço.

Em uma árvore muito larga, BFS também pode chegar a:

O(n)

25. Um detalhe importante sobre DFS recursivo

A implementação recursiva é muito elegante:

function traverse(node) {
  if (!node) {
    return;
  }

  traverse(node.left);
  traverse(node.right);
}

Mas cada chamada recursiva utiliza a Call Stack.

Em árvores extremamente profundas, isso pode causar:

Maximum Call Stack Size Exceeded

Nesses casos, podemos implementar DFS iterativamente utilizando uma pilha:

function preorder(
  root: TreeNode | null
): number[] {
  if (!root) {
    return [];
  }

  const result: number[] = [];
  const stack: TreeNode[] = [root];

  while (stack.length > 0) {
    const node = stack.pop()!;

    result.push(node.value);

    if (node.right) {
      stack.push(node.right);
    }

    if (node.left) {
      stack.push(node.left);
    }
  }

  return result;
}

Colocamos o right antes do left porque a pilha funciona em modo LIFO:

Last In
First Out

Assim, o left será processado primeiro.

26. Resumo dos Traversals

Considere:

        A
       / \
      B   C
     / \
    D   E

Os resultados são:

Preorder

Root → Left → Right

A → B → D → E → C

Inorder

Left → Root → Right

D → B → E → A → C

Postorder

Left → Right → Root

D → E → B → C → A

Level Order

Level by Level

A → B → C → D → E

27. Como memorizar?

Uma forma simples:

PRE

ROOT vem PREviamente

IN

ROOT fica INtermediário

POST

ROOT vem POSTeriormente

Ou simplesmente:

Preorder

ROOT → Left → Right


Inorder

Left → ROOT → Right


Postorder

Left → Right → ROOT

Já o BFS:

Level Order

Nível 1
↓
Nível 2
↓
Nível 3

28. Qual algoritmo escolher?

Podemos pensar assim:

Preciso percorrer uma árvore
            │
            ▼
    Preciso processar por nível?
         /          \
       Sim           Não
        │             │
        ▼             ▼
       BFS           DFS
                      │
          ┌───────────┼───────────┐
          ▼           ▼           ▼
       Preorder    Inorder    Postorder

Preorder

Use quando:

Root → Left → Right

É útil quando o pai precisa ser processado antes dos filhos.

Inorder

Use especialmente em:

Binary Search Tree

para processar os valores em ordem.

Postorder

Use quando:

Filhos → Pai

precisam ser processados nessa ordem.

BFS

Use quando:

Nível por nível

é importante.

Conclusão

Tree Traversal é o conjunto de técnicas utilizadas para percorrer todos os nós de uma árvore.

As duas principais categorias são:

DFS
│
├── Preorder
├── Inorder
└── Postorder

BFS
└── Level Order

No DFS, exploramos a árvore em profundidade.

No BFS, exploramos a árvore nível por nível.

Os três principais tipos de DFS são:

Preorder

Root → Left → Right

Inorder

Left → Root → Right

Postorder

Left → Right → Root

E o BFS mais comum:

Level Order

Nível → Nível → Nível

A principal lição é entender que a mesma árvore pode ser percorrida em diferentes ordens, e a ordem escolhida depende do problema que queremos resolver.

Se você precisa explorar caminhos e subárvores, pense em DFS. Se precisa processar a árvore por níveis ou encontrar algo pela menor distância em níveis, pense em BFS.