Non ho capito bene il tuo algoritmo.
tuttavia, ammesso che tu possa usare la ricorsione, che ne dici del seguente codice ?

codice:
static boolean isComplete(Node nd){

   if(nd == null) 
     return true;

  if(nd.getNumChildren() != 2) 
     return false;

  return isComplete(nd.getFirstChild()) && isComplete(nd.getSecondChild());

}