Поменять местами узел с максимальным ключом и узел, являющийся корнем дерева

[natatttt]

Помогите, пожалуйста!
Требуется создать сбалансированное дерево поиска, состоящее из целых чисел. Вывести информацию на экран, используя прямой, обратный и симметричный обход дерева. Выполнить задание, результат вывести на экран. В конце работы освободить всю динамически выделенную память.
Задание следующее: Поменять местами узел с максимальным ключом и узел, являющийся корнем дерева. Дополнить функцию exchange()

#include <iostream>
#include <Windows.h>
#include <stdio.h>
#include <io.h>
#include <iomanip>
using namespace std;

struct TNode
{
    int inf{}; //информационная часть узла
    TNode* left = nullptr; //адресная часть 
    TNode* right = nullptr; //адресная часть
    int depth = 1;
};

//проверка наличия элементов в дереве
bool empty(TNode* p) 
{ 
    if (p) return false;
    else return true;
}

//прямой обход дерева
void print_prym(TNode* p)
{
    if (!p) return;
    cout << p->inf << " ";
    print_prym(p->left);
    print_prym(p->right);
}

//симметричный обход дерева
void print_simm(TNode* p) 
{
    if (!p) return;
    print_simm(p->left);
    cout << p->inf << " ";
    print_simm(p->right);
}

//обратный обход дерева
void print_obr(TNode* p)
{
    if (!p) return;
    print_obr(p->left);
    print_obr(p->right);
    cout << p->inf << " ";
}

//чтение глубины поддерева
int dph(const TNode* p) 
{
    if (!p) return 0; //если поддерево отсутствует
    return p->depth;
}

//вычисление разбалансированности дерева
int bfactor(const TNode* p)
{
    return dph(p->right) - dph(p->left);
}

//вычисление глубины поддерева
void maxdepth(TNode* p) 
{
    int l = dph(p->left);
    int r = dph(p->right);
    if (l > r) p->depth = l + 1;
    else p->depth = r + 1;
}

//правый поворот вокруг узла p
TNode* rotate_right(TNode* root) 
{
    TNode* p = root->left;
    root->left = p->right;
    p->right = root;
    maxdepth(root);
    maxdepth(p);
    return p;
}
    
//левый поворот вокруг узла p
TNode* rotate_left(TNode* root) 
{
    TNode* p = root->right;
    root->right = p->left;
    p->left = root;
    maxdepth(root);
    maxdepth(p);
    return p;
}

//балансировка узла p
TNode* AVL(TNode* p) 
{
    maxdepth(p);
    if (bfactor(p) == 2)
    {
        if (bfactor(p->right) < 0) p->right = rotate_right(p->right);
        return rotate_left(p);
    }
    if (bfactor(p) == -2)
    {
        if (bfactor(p->left) > 0) p->left = rotate_left(p->left);
        return rotate_right(p);
    }
    return p; //балансировка не нужна 
}

//добавление эл-та в дерево
TNode* push(TNode* p, int key)
{
    if (!p)
    {
        p = new TNode;
        p->inf = key;
        return p;
    }
    if (key < p->inf) p->left = push(p->left, key);
    else p->right = push(p->right, key);
    return AVL(p);
}

//поиск узла с максимальным ключом
TNode* search_max(TNode* p) 
{
    TNode* q = p;
    while (q->right != nullptr) q = q->right;
    return q;
}

//обмен узла, имеющего максимальный ключ, с корнем дерева
TNode* exchange(TNode* p)
{

}
    
//удаление всего дерева
TNode* pop(TNode* p) 
{
    if (!p) return nullptr;
    pop(p->left);
    pop(p->right);
    delete(p);
}
                   
//вывод дерева на экран
void print(TNode* p, int r = 0) 
{
    if (!p) return;
    cout << setiosflags(ios::right);
    print(p->right, r + 5);
    cout << setw(r) << p->inf << endl;
    print(p->left, r + 5);
}

int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    TNode* root = nullptr; const int n = 10;
    for (int i = 1; i < n; i++) root = push(root, i * 2);
    print(root); // Выводит дерево
    cout << "___________________________________________________" << endl;
    cout << "Прямой обход дерева: ";
    print_prym(root);
    cout << endl;
    cout << "Симметричный обход дерева: ";
    print_simm(root);
    cout << endl;
    cout << "Обратный обход дерева: ";
    print_obr(root);
    cout << endl;
    cout << "___________________________________________________" << endl;
    TNode* max = search_max(root);
    cout << "Узел с максимальный ключом: " << max->inf << endl;
    cout << "___________________________________________________" << endl;
    exchange(root);
    root = pop(root);
    cout << endl;
    if (empty(root)) cout << "Дерево удалено";
    return 0;
}