verifica se uma árvore é uma árvore binária completa

Question

Tenho que escrever um algoritmo que verifique se uma árvore é uma árvore binária completa (cada nó, exceto as folhas, deve ter 2 filhos), mas não sei se esta versão está correta.

 isComplete(u) 
{
        if(u == NULL)
                return false
        else
        {
                left = isComplete(u.left);
                right = isComplete(u.right);
                complete = left && right;

                return complete.
        }
}

Answer 1

Como seu algoritmo é recursivo, você precisa considerar:

• o caso inicial/final:as folhas
• e o caso geral:os nós

Por exemplo, no caso de fatorial:

• o caso inicial $f(1) = 1$
• e o caso geral é $f(n) = n*f(n-1)$

Formalmente, para provar sua correção, você pode usar a indução.