is BST or not ?

Check whether the Binary tree is BST or not ?

Comments

  1. int 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))
    }

    ReplyDelete
  2. Its wrong....
    Counter 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.

    ReplyDelete
  3. @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..:)

    ReplyDelete
  4. int 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.

    ReplyDelete

Post a Comment

Popular posts from this blog