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?

score 6 · Answer 1 · answered Jan 31 '12 at 10:08

[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.

score 1 · Answer 2 · answered Jun 13 '12 at 17:08

You should call function as below. In which INT_MIN and INT_MAX are constant defined.

IsValidBST (root, INT_MIN, INT_MAX)

But this is approach will not work for all data. Means, data for which we don't know MIN and MAX values, like strings or any arbitrary user defined types.

To find out whether given BT is BST for any datatype, you need go with below approach. 1. call recursive function till the end of leaf node using inorder traversal 2. Build your min and max values yourself.

Provided that, tree element must have less than / greater than operator defined.

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
bool IsValidBST (treeNode *root, T *MIN , T *MAX)
{
   T leftMin, leftMax, rightMin, rightMax;
   bool isValidBST;

   if (root->leftNode == NULL && root->rightNode == NULL)
   {
      *MIN = root->element;
      *MAX = root->element;
      return true;
   }

  isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax);

  if (isValidBST)
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax);

  if (isValidBST)
  {
     *MIN = MIN (leftMIN, rightMIN);
     *Max = MAX (rightMax, leftMax);
  }

  return isValidBST;
}

score 0 · Answer 3 · answered Jan 31 '12 at 10:07

They have to be passed through the function in order for it to be called recursively with increasing reduced ranges as it is here.

Of course, for the first call, you could determine MIN and MAX from the tree, but for subsequent ones you must pass down like this.

score 0 · Answer 4 · edited Jun 13 '12 at 08:51

0

Here MIN MAX specifies the minimum value stored in tree and the maximum value stored in the tree.

I think simplest way to check the valid BST tree is traverse inorder and check if
the values are in sorted order or not? if all the values are in sorted order that
means its valid BST.

Implementation http://justprogrammng.blogspot.com/2012/06/check-if-tree-is-bst-on-code-interview.html

edited Jun 13 '12 at 08:51

sachin

203
4
9

answered Jan 31 '12 at 10:08

Hemant Metalia

29,730
18
72
91

that implementation fails a simple test. – Steve Jun 27 '13 at 11:54
A test case which fails is this: root.data = 3, has left child also with data = 3. This is valid but your code (I think, if I implemented correctly) says it is not. If you change the "<=" to "<" this fixes the bug. – Steve Jun 28 '13 at 12:09
@SteveHaigh Good It solved. It is not my code it is the code which was useful to me earlier. – Hemant Metalia Jul 01 '13 at 04:17

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

4 Answers4