FERRAMENTA · ESTRUTURAS DE DADOS

Travessia de árvore — playground

Compare in-ordem, pré-ordem, pós-ordem e BFS lado a lado em uma BST balanceada de 13 nós.

BST · n=13 · h=3 in-ordem
50 30 70 20 40 60 80 25 35 45 65 75 90
SEQUÊNCIA
20 25 30 35 40 45 50 60 65 70 75 80 90

VELOCIDADE

0.5×2.0×5×

ESTADO

ATUAL50
VISITADOS1 / 13
RESTANTES12
depth3

COMPLEXIDADE

timeO(n)
space (DFS)O(h) = O(log n)
space (BFS)O(w) = O(n/2)

Travessia DFS recursiva consome O(h) na pilha de chamadas. BFS consome O(w) onde w é a largura máxima — para árvores balanceadas, w = n/2.

INVARIANTE

Para cada nó n: chaves em sub-árvore esquerda < n.key < chaves em sub-árvore direita.