Спринт 10. Деревья и поиск.

#include <cassert>

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

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

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

template <typename T>
bool CheckTreeProperty(const TreeNode<T>* node, const T* min, const T* max) {

    bool check;

    if (min && node->left) {
        if(*min > node->left->value) {
            return false;
        }
    }

    if (max && node->right) {
        if (*max < node->right->value) {
            return false;
        }
    }

    if (!node->left && !node->right && node) {
        check = true;
        return check;

    } else if (!node->left && node->right && node) {
        check = node->value < node->right->value;

    } else if (node->left && !node->right && node) {
        check = node->value > node->left->value;

    } else {
        check = node->value < node->right->value && node->value > node->left->value;

    }

    if (node) {

        if(node->left) {
            check = CheckTreeProperty<T>(node->left, nullptr, &node->value) && check;
        }

        if(node->right) {
            check = CheckTreeProperty<T>(node->right, &node->value, nullptr) && check;
        }
    }

    return check;
}

int main() {
    using T = TreeNode<int>;
    T* root1 = new T{6,
        new T{4, new T{3}, new T{5}}, new T{7}};
    assert(CheckTreeProperty(root1));

    T* root2 = new T{6,
        new T{4, new T{3}, new T{5}}, new T{7, new T{8}}};
    assert(!CheckTreeProperty(root2));

    DeleteTree(root1);
    DeleteTree(root2);
}