#include <cassert>
#include <iostream>

using namespace std;

template<typename T>
struct TreeNode {
    T value;
    TreeNode *parent = nullptr;
    TreeNode *left = nullptr;
    TreeNode *right = nullptr;
};

template<class T>
void DeleteTree(TreeNode<T> *node) {
    if (!node) {
        return;
    }
    DeleteTree(node->left);
    DeleteTree(node->right);
    delete node;
}

template<class T>
void PrintTree(const TreeNode<T> *root, ostream &out = cout) {
    out << " ( "s;
    out << root->value;
    if (root->left || root->right) {
        if (root->left) {
            PrintTree(root->left, out);
        } else {
            out << "*"s;
        }
        if (root->right) {
            PrintTree(root->right, out);
        } else {
            out << "*"s;
        }
    }
    out << " ) "s;
}

template<class T>
ostream &operator<<(ostream &out, const TreeNode<T> *node) {
    PrintTree(node, out);
    return out;
}

template<class T>
TreeNode<T> *begin(TreeNode<T> *node) {
    auto tmp = node;
    while (tmp->left) tmp = tmp->left;
    return tmp;
}

template<class T>
TreeNode<T> *next(TreeNode<T> *node) {
    if (node->right) return begin(node->right);
    auto current = node;
    while (current->parent->left != current) {
        if (current->parent) current = current->parent;
        else return nullptr;
    }
    return current->parent;
}

// функция создаёт новый узел с заданным значением и потомками
TreeNode<int> *N(int val, TreeNode<int> *left = nullptr, TreeNode<int> *right = nullptr) {
    auto res = new TreeNode<int>{val, nullptr, left, right};
    if (left) {
        left->parent = res;
    }
    if (right) {
        right->parent = res;
    }

    return res;
}

template<typename T>
bool CheckTreeProperty(const TreeNode<T> *node, const T *min, const T *max) {
    if (!node) return true;
    if (min && node->value < *min) return false;
    if (max && node->value > *max) return false;
    return CheckTreeProperty(node->left, min, &node->value) && CheckTreeProperty<T>(node->right, &node->value, max);
}

template<typename T>
bool CheckTreeProperty(const TreeNode<T> *node) {
    return CheckTreeProperty<T>(node, nullptr, nullptr);
}

int main() {
    using T = TreeNode<int>;

    T *root = N(1, nullptr, N(2, nullptr, N(3, nullptr, N(4))));
    cout << root << endl;

    T *iter = begin(root);

    while (iter) {
        cout << iter->value << " "s;
        iter = next(iter);
    }
    cout << endl;

    DeleteTree(root);
}