Скопировать бинарное дерево, используя нерекурсивный алгоритм

#include <iostream>
#include <conio.h>
using namespace std;
//Наша структура
struct node
{
    int info;                           //Информационное поле
    node* l, * r;                        //Левая и Правая часть дерева
};
node* tree = NULL;                      //Объявляем переменную, тип которой структура Дерево
void push(int a, node** t)
{
    if ((*t) == NULL)                   //Если дерева не существует
    {
        (*t) = new node;                //Выделяем память
        (*t)->info = a;                 //Кладем в выделенное место аргумент a
        (*t)->l = (*t)->r = NULL;       //Очищаем память для следующего роста
        return;                         //Заложили семечко, выходим
    }
    //Дерево есть
    if (a > (*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
    else push(a, &(*t)->l);         //Иначе кладем его влево
}
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print(node* t, int u)
{
    if (t == NULL) return;                  //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
        print(t->l, ++u);                   //С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i < u; ++i) cout << "|";
        cout << t->info << endl;            //И показываем элемент
        u--;
    }
    print(t->r, ++u);                       //С помощью рекурсии посещаем правое поддерево
}
 
int main()
{
    setlocale(0, "rus");
    int n;                              //Количество элементов
    int s;                              //Число, передаваемое в дерево
    cout << "Введите количество элементов  ";
    cin >> n;                           //Вводим количество элементов
 
    for (int i = 0; i < n; ++i)
    {
        cout << "ведите число  ";
        cin >> s;                       //Считываем элемент за элементом
 
        push(s, &tree);                 //И каждый кладем в дерево
    }
    cout << "ваше дерево\n";
    print(tree, 0);
    cin.ignore().get();
}

#include <iostream>
#include <stack>
 
template<typename T>
struct Node {
    T value;
    Node<T> *left;
    Node<T> *right;
    Node(const T &value): value(value), left(nullptr), right(nullptr) {}
    Node(const T &value, Node<T> *left, Node<T> *right): value{value}, left{left}, right{right} {}
    Node<T> *insert(const T &value) {
        auto *newNode = new Node<T>(value);
        if (value < this->value) {
            if (left == nullptr) {
                left = newNode;
            } else {
                left->insert(value);
            }
        } else {
            if (right == nullptr) {
                right = newNode;
            } else {
                right->insert(value);
            }
        }
        return newNode;
    }
};
 
template<typename T, typename Callback>
void traverse(Node<T> *root, Callback callback) {
    std::stack<Node<T>*> stack;
    stack.push(root);
    while (!stack.empty()) {
        root = stack.top();
        callback(root->value);
        stack.pop();
        if (root->left != nullptr) {
            stack.push(root->left);
        }
        if (root->right != nullptr) {
            stack.push(root->right);
        }
    }
}
 
template<typename T, typename Callback>
void traverseInOrder(Node<T> *root, Callback callback) {
    std::stack<Node<T>*> stack;
    while (root != nullptr || !stack.empty()) {
        while (root != nullptr) {
            stack.push(root);
            root = root->left;
        }
        root = stack.top();
        callback(root->value);
        stack.pop();
        root = root->right;
    }
}
 
int main() {
    Node<int> root(0);
 
    root.insert(-5);
    root.insert(-8);
    root.insert(-3);
    root.insert(5);
    root.insert(8);
    root.insert(3);
 
    traverse(&root, [](auto &value){ std::cout << value << " ";});
    std::cout << std::endl;
    traverseInOrder(&root, [](auto &value){ std::cout << value << " ";});
 
    return 0;
}