Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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, const T* min, const T* max) {
- bool result = true;
- if (node->left != nullptr) {
- if (node->left->value > node->value || (max && node->left->value > *max)) {
- return false;
- }
- else {
- result = CheckTreeProperty(node->left, min, &node->value);
- }
- }
- if (result && node->right != nullptr) {
- if (node->right->value < node->value || (min && node->right->value < *min)) {
- return false;
- }
- else {
- result = CheckTreeProperty(node->right, &node->value, max);
- }
- }
- return result;
- }
- template <typename T>
- bool CheckTreeProperty(const TreeNode<T>* node) {
- return CheckTreeProperty<T>(node, nullptr, nullptr);
- }
- 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);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
