is BST or not ? Get link Facebook X Pinterest Email Other Apps By Admin - December 14, 2010 Check whether the Binary tree is BST or not ? Get link Facebook X Pinterest Email Other Apps Comments AdminDecember 14, 2010 at 4:15 PMint isBST(struct node *root){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))}ReplyDeleteRepliesReplyGauravDecember 20, 2010 at 8:42 PMIts wrong.... Counter test case : 5 / \ 2 6/ \1 9Its not BST... ur code will return true.U will have to keep a max and min of a subtree too.ReplyDeleteRepliesReplyAdminDecember 20, 2010 at 9:01 PM@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..:)ReplyDeleteRepliesReplyAdminDecember 20, 2010 at 9:30 PMint isBST(struct node* node, int min, int max){ /* 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.ReplyDeleteRepliesReplyAdd commentLoad more... Post a Comment
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.