What are "min" and "max" in this function to check if a binary tree is a valid BST?

Question

The below code is from Finding if a Binary Tree is a Binary Search Tree.

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
     return true;

    if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

How are MIN and MAX being used here? What values do they represent? And why would they need to be passed through the function?

Answer 1

[MIN, MAX] represents the range in which a valid value in the current node could be. For the first node this would be INT_MIN and INT_MAX because it can have arbitrary values, but for its children we need to check the BST property - all the left children should not be greater then the current node and all the right ones should not be less. That is why we change the MIN and MAX values for them respectvely.

NOTE: if in the tree you can have repeating values, change the check to:

 if(node.element >= MIN 
   && node.element <= MAX
   && IsValidBST(node.left,MIN,node.element)
   && IsValidBST(node.right,node.element,MAX))

Or you will get invalid results.