CareerCup

bool isBST(Node* node){
if(node==NULL)
return TRUE;
else if(node->left->data>node->data || node->right->data<node->data)
return FALSE;
else return(isBST(node->left) && isBST(node->right));
}

Good one ... traverse the tree in in-order fashion and each time compare value of current node with previous node.

Though special consideration required for ensuring values in the lest subtree can be less than or equal to parent while value in right can only be greater (and not equal to) parent.

Boolean isBST(Tree* node)
{
if(node == NULL)
return true;
else if (node->left->data < node->data && node->right->data >= node->data)
return isBST(node->left) && isBST(node->right);
}

Of course u need checking to make sure u dont dereference a null pointer.

The above method will not work. consider a tree like this
{root} = 1 {2,10} // 2 is left child, 10 is right child
{10} = 10 {3,11} // Even though locally the conditions stisfy, globally its not a BST. Here 3 < 10 but it is in the wrong side of the root.

Boolean isBST(Tree *node, int & minVal) {
if (node == NULL)
return true;
if (!isBST(node->left, minVal)
return false;
if (minVal > this->data)
return false;
minVal = this->data;
if (!isBST(node->right, minVal)
return false;
return true;
}

call this function as
int minVal = MIN_INT;
// pass minVal by reference
isBST(root, minVal);
//or whatever is the least possible value of data

simple: Do an inorder traversal (left, root, right) of the tree and if the values are in ascending order then the tree is a binary search tree.

I htink SP's solution will work

Nitu,

SP's solution will not work. It checks all {left, root, right } pairs in isolation. Consider this tree

4
/ 2 6
/ \ / 1 5 3 7

5 and 3 in wrong places (compare to 4) but SP's solution will still declare this as BST.

Nitu,

SP's solution will not work. It checks all {left, root, right } pairs in isolation. Consider this tree

4
/ 2 6
/ \ / 1 5 3 7

5 and 3 in wrong places (compare to 4) but SP's solution will still declare this as BST.

Nitu,

SP's solution will not work. It checks all {left, root, right } pairs in isolation. Consider this tree

4
/ 2 6
/ \ / 1 5 3 7

5 and 3 in wrong places (compare to 4) but SP's solution will still declare this as BST.

sorry, the previous post's formatting was goofed up.
here's the tree:

______4
___2____6
__1_5__3_7

From the link below:
cslibrary.stanford.edu/110/BinaryTrees.html#csoln

/*
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

// (bug -- an earlier version had min/max backwards here)
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);
}

we cant do an inorder traversal of the tree and chk for the ascending values as a check fo the tree as - If we have many elements in the order of millions, then we would need an equally huge data structure like a stack or a linked list to store the numbers of the inorder traversal.

I think inorder traversal will work and you don't need a huge DS to store all the numbers.Just maintain two variable & compare currently read variable from the tree with the previously read var,if currently read is always greater than the prev read till we read the entire tree, it is BST, otherwise not.

the code is in perl but works fine

sub isBST {
    my ($tree) = @_;
    return 1 unless($tree);
    if ($tree->{LEFT}) {
        if ($tree->{LEFT}->{VALUE} > $tree->{VALUE}) {
            return 0;
        }
    }
    if ($tree->{RIGTH}) {
        if ($tree->{RIGTH}->{VALUE} < $tree->{VALUE})  {
            return 0;
        }
    }
    return isBST($tree->{LEFT}) && isBST($tree->{RIGHT});
}