a function to verifies if the values are correctly ordered in the tree

[momotaro]

am trying to implimente a function to check weither a function is bst or not this is my code PLZ HELP:

int CheckOrder(TreeNode *root){
if (!root)
   return TRUE;
if (CheckOrder(root->left->entry) < root->entry &&
    CheckOrder(root->right->entry) > root->entry)
    CheckOrder(root->left);
    CheckOrder(root->right);
    return TRUE;
else
     return FALSE;
}

[momotaro]

sorry this is the right one:

int CheckOrder(TreeNode *root){
if (!root)
   return TRUE;
if (CheckOrder(root->left->entry) < root->entry &&
    CheckOrder(root->right->entry) > root->entry){
    CheckOrder(root->left);
    CheckOrder(root->right);
    return TRUE;
}
else
     return FALSE;
}

[/quote]

[Strika Amaru]

Not to split hairs, but aren't the code snippets identical? :)
The problem probably is that you're comparing the bool returned by CheckOrder with the value of root->entry. So: (i haven't tested this)

int CheckOrder(TreeNode *root){
if (!root)
   return TRUE;
// in here you have to check for the existence of the left & right..
//no simple and elegant way around it.
if ( (root->left !=NULL && root->left->entry < root->entry) &&
    (root->right!=NULL && root->right->entry) > root->entry) ) {
    CheckOrder(root->left);
    CheckOrder(root->right);
    return TRUE;
}
else
     return FALSE;
}

[JosAH]

Not to split hairs, but aren't the code snippets identical? :)
The problem probably is that you're comparing the bool returned by CheckOrder with the value of root->entry. So: (i haven't tested this)

int CheckOrder(TreeNode *root){
if (!root)
   return TRUE;
// in here you have to check for the existence of the left & right..
//no simple and elegant way around it.
if ( (root->left !=NULL && root->left->entry < root->entry) &&
    (root->right!=NULL && root->right->entry) > root->entry) ) {
    CheckOrder(root->left);
    CheckOrder(root->right);
    return TRUE;
}
else
     return FALSE;
}

The intention is right but the implementation is wrong ;-) Suppose a tree just
has a right sub-tree: that if-clause causes a wrong conclusion then. Even worse:
it ignores the return values of the recursive calls.

Better split the tests up like this:

if (!root || !root->left && !root->right) return TRUE; // empty of a leaf
 
if (root->left)
   if (root->left->data <= root->data)
      return Checkorder(root->left);
   else 
      return FALSE;
else if (root->right->data >= root->data)
   return Checkorder(root->right);
else
   return FALSE;

kind regards,

Jos