//validate binarySearchTree class Node { public: int value; Node* left; Node* right; } //recursive bool isBinarySearchTreeRecursive(Node* currentNode, int min, int max) { if(currentNode->value >= max || currentNode->value left != NULL) { retValue = isBinarySearchTree(currentNode->left, min, currentNode->value); } //look at right if(retValue == true && currentNode->right != NULL) { retValue = isBinarySearchTree(currentNode->right, currentNode->value, max); } return retValue; } //iterative class NodeCheck { public: Node *currentNode; int min; int max; NodeCheck(Node* inNode, int inMin, int inMax) : currentNode(inNode), min(inMin), max(inMax){} bool isValidNode() { return (currentNode->value value > min) } } bool isBinarySearchTreeIterative(Node* root) { queue myQ; NodeCheck newN(root, 0, INT_MAX); myQ.push_back(newN); while(!myQ.empty()) { NodeCheck currNC = myQ.front(); myQ.pop(); if(!currNC.isValidNode()) { return false; } //insert left if(currNC.Node->left != NULL) { NodeCheck newN(currNC.Node->left, currNC.min, currNC.Node->value); } //insert right if(currNC.Node->right != NULL) { NodeCheck newN(currNC.Node->right, currNC.Node->value, currNC.max); } } return true; }