O menor ancestral comum entre dois nós de uma BST n_{1} e n_{2} é o ascendente de n_{1} e n_{2} que está mais próximo deles. Faça um algoritmo que encontre o menor ancestral comum de dois nós de uma BST e analise o tempo de seu algoritmo. Considere que os valores n_{1} e n_{2} pertencem à BST.
Passo 1
O enunciado pede um algoritmo para encontrar o menor ancestral comum (LCA, do inglês “lowest common ancestor”) de dois nós de valores n_{1} e n_{2} em uma árvore de busca binária (BST). Vamos usar a propriedade fundamental de BST — todos os valores à esquerda de um nó são menores que o valor do nó e todos os valores à direita são maiores — para guiar a busca pelo LCA.
Passo 2
A ideia é percorrer a árvore a partir da raiz e, em cada nó T com valor \,T.\text{val}:
se n_{1} e n_{2} são ambos menores que T.\text{val}, então o LCA está no ramo esquerdo;
se n_{1} e n_{2} são ambos maiores que T.\text{val}, então o LCA está no ramo direito;
caso contrário (um valor de cada lado ou um igual a T.\text{val}), T é o menor ancestral comum.
Passo 3
Aqui está o pseudocódigo do algoritmo em definição recursiva:
Análise de tempo: a cada chamada recursiva descemos um nível da árvore. Se a altura da BST é h, o algoritmo faz no máximo h comparações antes de parar.
Em média, em uma BST balanceada, h = O(\log n); no pior caso (árvore degenerada), h = O(n). Portanto, o tempo de execução é
O algoritmo recorre da raiz seguindo à esquerda ou à direita conforme n_{1} e n_{2} serem menores ou maiores que o valor do nó, e retorna o primeiro nó em que eles ficam em lados diferentes (ou igual a um deles). O tempo de execução é O(h), onde h é a altura da árvore (O(\log n) em média, O(n) no pior caso).