Построить бинарное дерево по строке. Выполнить балансировку данного дерева

#include <iostream>
#include <sstream>
#include <stack>
#include <queue>
 
using namespace std;
 
// структура для представления узла бинарного дерева
struct Node {
    int val;
    Node* left;
    Node* right;
    bool is_leaf; // флаг, указывающий, является ли узел листовым 
    Node(int v) : val(v), left(nullptr), right(nullptr), is_leaf(false) {}
};
 
// функция для построения бинарного дерева по строке s
Node* build_tree(string s) {
    stack<Node*> st;
    Node* root = new Node(0);
    Node* curr = root;
    for (char c : s) {
        if (isdigit(c)) { // добаляем узел со значением
            int val = c - '0';
            while (isdigit(s[1])) { // если значение состоит из нескольких цифр
                val = val * 10 + (s[1] - '0');
                s = s.substr(1); // обрезаем строку
            }
            Node* node = new Node(val);
            if (curr->left == nullptr) curr->left = node;
            else curr->right = node;
            st.push(curr);
            curr = node;
        } else if (c == '*') { // добаляем листовой узел
            Node* node = new Node(0);
            node->is_leaf = true;
            if (curr->left == nullptr) curr->left = node;
            else curr->right = node;
        } else if (c == ',') { // переходим к родительскому узлу
            if (!st.empty()) {
                curr = st.top();
                st.pop();
            }
        }
    }
    return root->left;
}
 
// функция для проверки, является ли дерево сбалансированным
bool is_balanced(Node* root) {
    if (root == nullptr) return true;
    int left_height = height(root->left);
    int right_height = height(root->right);
    return abs(left_height - right_height) <= 1 &&
           is_balanced(root->left) && is_balanced(root->right);
}
 
// функция для вычисления высоты дерева
int height(Node* root) {
    if (root == nullptr) return 0;
    return max(height(root->left), height(root->right)) + 1;
}
 
// функция для правого поворота поддерева, заданного корнем node 
Node* rotate_right(Node* node) {
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    return temp;
}
 
// функция для левого поворота поддерева, заданного корнем node 
Node* rotate_left(Node* node) {
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    return temp;
}
 
// функция для балансировки дерева
Node* balance_tree(Node* root) {
    if (root == nullptr) return nullptr;
    // балансируем левое поддерево
    root->left = balance_tree(root->left);
    // балансируем правое поддерево
    root->right = balance_tree(root->right);
    // проверяем, нужна ли балансировка
    int balance = height(root->left) - height(root->right);
    if (balance > 1) {
        // нужен поворот вправо
        if (height(root->left->left) >= height(root->left->right)) {
            root = rotate_right(root);
        } else { // нужен двойной поворот вправо
            root->left = rotate_left(root->left);
            root = rotate_right(root);
        }
    } else if (balance < -1) {
        // нужен поворот влево
        if (height(root->right->right) >= height(root->right->left)) {
            root = rotate_left(root);
        } else { // нужен двойной поворот влево
            root->right = rotate_right(root->right);
            root = rotate_left(root);
        }
    }
    return root;
}
 
// функция для обратного обхода дерева и формирования строки
string to_string(Node* root) {
    if (root == nullptr) return "";
    stringstream ss;
    if (root->is_leaf) {
        ss << "*";
    } else {
        ss << root->val;
        if (root->left != nullptr || root->right != nullptr) {
            ss << "(" << to_string(root->left) << "," << to_string(root->right) << ")";
        }
    }
    return ss.str();
}
 
// функция для вывода дерева в виде строки
string print_tree(Node* root) {
    root = balance_tree(root); // сначала балансируем дерево
    return to_string(root);
}
 
int main() {
    string s = "432*7**8**9*";
    Node* root = build_tree(s);
    string s_balanced = print_tree(root);
    cout << s_balanced << endl; // должно вывести: 4(3(*,2(*,*)),9(*,8(7(*,*),*)))
    return 0;
}