Бинарное дерево поиска на C/C++

Есть задачка. Имеется бинарное дерево. Требуется определить, является ли это дерево бинарным деревом поиска. Желательно представить решение на языке С++ или С. Оцениваются временная и пространственная сложность алгоритма, а так же универсальность подхода.

Ответ

UPD: моя неправда, исправляю. Предположим, что дерево определено так: struct BinaryTreeNode { BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), parent(NULL), value(val) {}
BinaryTreeNode * leftChild; BinaryTreeNode * rightChild; BinaryTreeNode * parent; int value; }; Тогда алгоритм проверки будет следующим: bool isBST(BinaryTreeNode * root) { return isBST_(root, 0, 0); }
bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent) { if (minParent && minParent->value >= node->value) return false; if (maxParent && maxParent->value <= node->value) return false; if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node)) return false; if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent)) return false; return true; } Временная сложность O(n), где n — количество узлов в дереве. Пространственная сложность O(h), где h — глубина дерева.