is BST or not ?
Check whether the Binary tree is BST or not ?
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
int isBST(struct node *root)
ReplyDelete{
if(root == NULL) return 1;
else if(root->left->value > root->value || root->right->value < root->value) return 0;
else return(isBST(root->left) && isBST(root->right))
}
Its wrong....
ReplyDeleteCounter test case :
5
/ \
2 6
/ \
1 9
Its not BST... ur code will return true.
U will have to keep a max and min of a subtree too.
@gaurav yes this code takes care of left and right child if misplaced.if you want to check if tree is correctly formed then you will have to keep track of min and max value.agreed..:)
ReplyDeleteint isBST(struct node* node, int min, int max)
ReplyDelete{
/* an empty tree is BST */
if (node==NULL)
return 1;
/* false if this node violates the min/max constraint */
if (node->data < min || node->data > max)
return 0;
return
isBST(node->left, min, node->data) &&
isBST(node->right, node->data+1, max);
}
call isBST(node,INT_MIN, INT_MAX) initially.