Nii Mante
BAN USER1. Check to see if the node is greater than or equal to max value of the left subtree
2. Check to see if the node is less than the minvalue of the right subtree
3. Check to see if the left or right subtrees are invalid
4. if all tests pass, then return true
template <class T>
bool validateBST(BinaryNode<T> *node){
if(node == NULL){
return true;
}
//If the max value of the left subtree is bigger than the node return false
//If the min value of the right subtree is smaller than the node return false
if(node->right != NULL && node->data < maxValue(node->right) ||
node->left != NULL && node->data >= minValue(node->left))
{
return false;
}
//check if either of the trees are invalid
//if any subtree is invalid, return false
if(!validateBST(node->left) || !validateBST(node->right)){
return false;
}
//we passed all the tests, so its valid :)
return true;
}
//Caller must make sure to not pass a NULL node
template <class T>
int maxValue(BinaryNode<T> *node){
//Recursively traverse down to the right node
//When we're at the current node, check if it's right child is null
//if the right child is null, then that means were the max
return (node->right == NULL) ? node->data : maxValue(node->right);
}
//Caller must make sure to not pass a NULL node
template <class T>
int minValue(BinaryNode<T> *node){
//Recursively traverse down to the left node
//When we're at the current node, check if it's left child is null
//if the left child is null, then that means the current node is the min
return (node->left == NULL) ? node->data : minValue(node->left);
}
My methodology was to:
1. Generate each range of integers
2. Add the ranges to a python set (that way you have unique integers)
3. Sort the python set into a list
4. Walk the sorted list
a. if there's a difference between adjacent elements > 1
then print the two elements separated by a "], [" string
b. if it's the beginning or end of the list,
then print a '[' + the element or print a ']' + the element
- Nii Mante February 09, 2015