Итеративное копирование бинарного дерева

Мне задали этот вопрос в интервью, и это буквально стоило мне работы: п Интервьюер спросил, что вам дадут корень дерева, и вы должны вернуть корень скопированному дереву, но копия должна быть сделана итеративно. Я вставляю свой код здесь, я написал то же самое там, и он отлично работает. Сначала я сделал это, используя два стека, которые, по словам интервьюера, ему не понравились, затем я сделал это следующим образом. Интервьюер был немного недоволен тем, что я использовал другую структуру, которая содержит указатель на исходное и окончательное дерево (см. код).

Мне интересно, есть ли другой, лучший способ сделать это??

struct node
{
   int data;
   struct node * left;
   struct node * right;
};

struct copynode
{
   node * original;
   node * final;
};

node * copy(node *root)
{
    stack <copynode*> s;
    copynode * temp=(copynode*)malloc(sizeof(copynode));
    temp->original=root;
    temp->final=(node *)malloc(sizeof(node));
    s.push(temp);
    while(s.empty()==false)
    {
       copynode * i;
       i=s.top();
       s.pop();
       i->final=i->original;
       if(i->original->left)
       {
          copynode *left=(copynode*)malloc(sizeof(copynode));
          left->original=i->original->left;
          left->final=(node *)malloc(sizeof(node));
          s.push(left);
       }
       if(i->original->right)
       {
          copynode *right=(copynode*)malloc(sizeof(copynode));
          right->original=i->original->right;
          right->final=(node *)malloc(sizeof(node));
          s.push(right);
       }
   }  
   return temp->final;
}