Спринт 11. Умный указатель unique_ptr. Задание 2.

-----------------------------------------------------------------------
tree.cpp
-----------------------------------------------------------------------
#include <cassert>
#include <iostream>
#include <memory>

template <typename T>
struct TreeNode;

template <typename T>
using TreeNodePtr = std::unique_ptr<TreeNode<T>>;

template <typename T>
struct TreeNode {

    TreeNode(T val, TreeNodePtr<T>&& left, TreeNodePtr<T>&& right) : value(std::move(val))
                                                                   , left(std::move(left))
                                                                   , right(std::move(right)) {}

    T value;
    TreeNodePtr<T> left;
    TreeNodePtr<T> right;
    TreeNode* parent = nullptr;
};

template <typename T>
bool CheckTreeProperty(const TreeNode<T>* node) noexcept {
    if(node->parent){

        if (node->parent->left.get() != node) {
            if (node->parent->value > node->value) {
                return false;
            }
        }

        if (node->parent->right.get() != node) {
            if (node->parent->value < node->value) {
                return false;
            }
        }
    }

    if (!(node->left.get()) && !(node->right.get())) {

        return true;

    } else if (node->left.get() && node->right.get()) {

        return CheckTreeProperty<T>(node->left.get()) &&
               CheckTreeProperty<T>(node->right.get());

    } else if (!(node->left.get())) {

        return CheckTreeProperty<T>(node->right.get());

    } else {

        return CheckTreeProperty<T>(node->left.get());

    }
}

template <typename T>
TreeNode<T>* begin(TreeNode<T>* node) noexcept {

    while (node->left!=nullptr) {
        node = node->left.get();
    }

    return node;
}

template <typename T>
TreeNode<T>* next(TreeNode<T>* node) noexcept {

    if (node->right) {

        return begin(node->right.get());
    }

    TreeNode<T>* _node = node->parent;

    while (_node && node == _node->right.get()) {
        node = _node;
        _node = _node->parent;
    }

    return _node;
}

TreeNodePtr<int> N(int val, TreeNodePtr<int>&& left = {}, TreeNodePtr<int>&& right = {}) {

    auto helper = new TreeNode<int>(val, std::move(left), std::move(right));
    std::unique_ptr<TreeNode<int>> treenode_uniq{helper};

    if (treenode_uniq->left) {
        treenode_uniq->left->parent = helper;
    }

    if (treenode_uniq->right){
        treenode_uniq->right->parent = helper;
    }

    return treenode_uniq;
}

int main() {
    using namespace std;
    using T = TreeNode<int>;
    auto root1 = N(6, N(4, N(3), N(5)), N(7));
    assert(CheckTreeProperty(root1.get()));

    T* iter = begin(root1.get());
    while (iter) {
        cout << iter->value << " "s;
        iter = next(iter);
    }
    cout << endl;

    auto root2 = N(6, N(4, N(3), N(5)), N(7, N(8)));
    assert(!CheckTreeProperty(root2.get()));
}