Árvores binárias são árvores nas quais cada nodo pode ter no máximo dois filhos, conforme mostrado na figura abaixo.

Uma árvore binária pode ser definida de forma recursiva, de acordo com o raciocínio a seguir. A raiz da árvore possui dois filhos, um à direita e outro à esquerda, que por sua vez são raizes de duas sub-árvores. Cada uma dessas sub-árvores possui uma sub-árvore esquerda e uma sub-árvore direita, seguindo esse mesmo raciocínio.

Árvores binárias de pesquisa (ou Binary Search Tress - BSTs, do Inglês) são árvores cujos nodos são organizados de acordo com algumas propriedades. Mais formalmente, podemos definir árvores binárias de pesquisa como abaixo:

Definição de Árvore Binária de Pesquisa: Seja $x$ um nodo em uma árvore binária de pesquisa. Se $y$ é um nodo na sub-árvore esquerda de $x$, então $y.chave \leq x.chave$. Se $y$ é um nodo na sub-árvore direita de $x$, então $y.chave \geq x.chave.$

Em outras palavras, árvores binárias de pesquisa são árvores que obedecem às seguintes propriedades:

Para simplificar as coisas, não permitiremos elementos repetidos em nossas implementações de BSTs, portanto, nodos à esquerda de um nodo sempre serão menores que ele, e nodos à direita de um nodo serão sempre maiores que ele.

Caminhamentos em árvore são formas de visitarmos todos os nodos de uma árvore em uma ordem pré-definida. Existem três tipos de caminhamentos básicos: pré-ordem, em ordem, e pós-ordem. Esses três tipos de caminhamentos são bem parecidos, como veremos abaixo.

Começaremos nossa explicação com o caminhamento em ordem. Nesse tipo de caminhamento, visitamos recursivamente o nodo da esquerda, visitamos o nodo corrente, e visitamos recursivamente o nodo da direita. Assim, dadas as restrições de uma árvore binária de pesquisa, ao realizarmos o caminhamento em ordem, estaremos de fato visitando os nodos em ordem crescente de chaves. Entretanto, os três tipos de caminhamentos explicados aqui podem ser usados para qualquer tipo de árvore. A única diferença é que ordem em que os nodos serão impressos. Por exemplo, o caminhamento em ordem em uma BST imprime os nodos em ordem crescente, mas em uma árvore binária qualquer a ordem pode não ser essa.

Para ilustrar o caminhamento em ordem, primeiro construiremos uma árvore binária de pesquisa:

Note que obedecemos as propriedades de árvores binárias de pesquisa ao inserirmos os nodos na árvore acima.

A figura ao lado mostra uma representação visual da árvore construída acima.

Agora, vejamos como implementar o caminhamento em ordem.

O código acima é uma implementação direta da ideia de caminhamento em ordem. Vejamos o que acontece ao executarmos o código acima na árvore criada anteriormente:

Neste momento, é importante fazermos uma ressalva: ao explicar o caminhamento em ordem dizemos que visitamos o nodo corrente, mas na implementação acima simplesmente imprimimos o valor do campo chave de cada nodo. Isso ocorre porque o termo visitar pode significar tanto algo simples como imprimir o valor da chave, quanto realizar alguma operação mais complexa. A ideia geral do caminhamento em ordem não muda, independente das operações que são realizadas quando visitamos um nodo.

Os outros dois tipos de caminhamento seguem o mesmo raciocínio do caminhamento em ordem. A única diferença é a ordem em que visitamos o nodo corrente. No caminhamento pré-ordem, visitamos o nodo corrente antes de visitarmos recursivamente os nodos da esquerda e direita. No caminhamento pós-ordem visitamos o nodo corrente depois de visitarmos recursivamente os nodos da esquerda e direita. A figura abaixo resume os três tipos de caminhamentos em árvores.

Antes de discutirmos complexidade assintótica de procedimentos que operam sobre árvores binárias, precisamos definir o que é uma árvore balanceada. A necessidade dessa definição ficará clara abaixo.

Definição: Uma árvore binária é balanceada se a diferença da profundidade de duas folhas quaisquer é no máximo 1. A profundidade de um nodo é o número de níveis da raiz até aquele nodo.

Na figura ao lado, a árvore a) é balanceada, e a árvore b) não é balanceada.

Se uma árvore é balanceada, tanto no caso da inserção quando no caso da busca, a cada chamada recursiva do algoritmo, descartamos metade da árvore original. Portanto, a complexidade assintótica desses dois procedimentos é logarítmica no tamanho (número de nodos) da árvore. Na verdade, muitos procedimentos que operam sobre árvores binárias de pesquisa funcionam com base nessa mesma ideia de eliminar metade da árvore a cada etapa do procedimento. Isso ocorre por causa da natureza recursiva das árvores binárias de pesquisa e pela forma como os nodos são inseridos nelas.

Entretanto, se a árvore não for balanceada, não descartaremos metade da árvore original a cada chamada recursiva. Em casos como o da árvore não balanceada mostrada acima, a complexidade dos procedimentos de inserção e busca será linear no tamanho da árvore, pois, na prática, a árvore mostrada funciona como se fosse uma lista encadeada.

No caso de árvores binárias, é importante sempre fazer a distinção da complexidade dos procedimentos caso a árvore seja balanceada e caso ela não seja. Além disso, é importante estar atento a procedimentos que parecem logarítmicos, mas que na verdade visitam todos os nodos da árvore. Para resumir, tenha em mente as seguintes situações:

Existe uma forma alternativa de se analisar a complexidade de operações em árvores e que dependem de a árvore ser ou não balanceada. Essa alternativa consiste de descrevermos a complexidade assintótica das operações não em termos do tamanho (número de nodos) da árvore, mas em termos da altura (número de níveis) da árvore. A altura de uma árvore balanceada, como a mostrada na parte a) da figura anterior, será $O(\log n)$, mas se a árvore não for balanceada, como a mostrada na parte b) da figura anterior, a altura será $O(n)$. A escolha de se analisar a complexidade em termos do tamanho da árvore ou de sua altura é uma escolha sua. Mas seja qual for a sua escolha, tenha em mente que, dependendo da forma como os nodos estiverem organizados na árvore, as operações podem ser logarítmicas ou lineares.

Uma árvore (note que aqui não estamos falando de BST) é simétrica se a subárvore esquerda for um espelho da subárvore direita. A figura abaixo mostra uma árvore simétrica, na parte a), e uma árvore não simétrica, na parte b).