Feb 26, 2009

check the binary tree is binary search tree

isBST2() Solution (C/C++)
/*
Returns true if the given tree is a binary search tree

*/
int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);

// false if this node violates the min/max constraint
if (node->datadata>max) return(false);

// otherwise check the subtrees recursively,
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}

No comments:

Post a Comment