"Write an algorithm to test whether a given binary tree is a binary search tree."
A binary search tree (BST) is a node based binary tree data structure which has the following properties.
/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node) {
if (node == NULL)
return(true);
/* false if the max of the left is > than us */
if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);
/* false if the min of the right is <= than us */
if (node->right!=NULL && minValue(node->right) < node->data)
return(false);
/* false if, recursively, the left or right is not a BST */
if (!isBST(node->left) || !isBST(node->right))
return(false);
/* passing all that, it's a BST */
return(true);
}
Why Required of ISO 9001:2000 standard?
