checks if a tree is a full binary tree

Question

I have to write an algorithm that checks if a tree is full binary tree (each node, except the leaves, must have 2 children), but I don't know if this version is correct.

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

                return complete.
        }
}

Answer 1

Since your algorithm is recursive you need to consider:

• the initial / final case : the leaves
• and the general case : the nodes

For example in the case of factorial:

• the initial case $f(1) = 1$
• and the general case is $f(n) = n*f(n-1)$

Formally, to prove its correctness you can use induction.