CareerCup

This can be solved by using recursive approach. For each node, compare its value to left and right child. and "AND" all the possible outcomes. if it returns false for any single node then it is not BST, else BST.

- sur February 03, 2010 | Flag Reply

The only way I can think of is inorder traversal and check for sortedness. There is no way not to track the nodes in the tree since the last leaf node in the tree might be greater than any of its ancestors.

- Anonymous February 02, 2010 | Flag Reply

The only way I can think of is inorder traversal and check for sortedness. There is no way not to track the nodes in the tree since the last leaf node in the tree might be greater than any of its ancestors.

- Anonymous February 02, 2010 | Flag Reply

{{{ bool IsBst(Tree *t) { return ISBstInternal(t,-infinity, +infinity); } bool IsBstInternal(Tree *t, int l, int r) { if(!t) return true; bool l = IsBstInternal(t->left, l, t->value); bool r = IsBstInternal(t->right, t->value, r); return l && r; } - Anonymous February 04, 2010 | Flag Reply

Aargh. Fix formatting.

bool IsBst(Tree *t)
{
    return ISBstInternal(t,-infinity, +infinity);
}
    
bool IsBstInternal(Tree *t, int l, int r)
{
    if(!t) return true;
    
    bool l = IsBstInternal(t->left, l, t->value);
    bool r = IsBstInternal(t->right, t->value, r);
    
    return l && r; 
}

- Anonymous February 04, 2010 | Flag Reply

bool verifyTree(Node root){
     if(root == null){
        return true;
     }
     Node l = root.getLeft();
     Node r = root.getRight();
     if(l.getValue() <= root.getValue() <= r.getValue()){
       return (verifyTree(l) && verifyTree(r));
     }
     else{
       return false;
     }
}

- XeqtR February 19, 2010 | Flag Reply

What about the following approach:

static int max_so_far = -infinity;
public isBST(Node root) {
if (root==null) return true;
boolean leftBST = isBST(root.left);
if (root.value>max_so_far) {
max_so_far = root.value;
}
else {
return false;
}
return leftBST && isBST(root.right);
}

- soupnazi August 22, 2010 | Flag Reply

I meant:

static int max_so_far = -infinity;
public isBST(Node root) {
   if (root==null) return true;
   boolean leftBST = isBST(root.left);
   if (root.value>max_so_far) {
      max_so_far = root.value;
   }
   else {
      return false;
   }
   return leftBST && isBST(root.right);
}

- Anonymous August 22, 2010 | Flag Reply

bool isBST(Tree *rt,int val,int flag)
{
if (rt == NULL) return true;

if ( rt->left != NULL)
{
if (rt -> data <= (rt->left)->data) return false;
if(flag ==1 && (rt->left)->data < val) return false;
}

if ( rt->right != NULL)
{
if (rt -> data > (rt->right)->data) return false;
if(flag ==0 && (rt->right)->data >= val) return false;

}

- ashish December 03, 2010 | Flag Reply

**ignore previous code

bool isBST(Tree *rt,int val,int flag)
{
if (rt == NULL) return true;

if ( rt->left != NULL)
{
if (rt -> data <= (rt->left)->data) return false;
if(flag ==1 && (rt->left)->data < val) return false;
}

if ( rt->right != NULL)
{
if (rt -> data > (rt->right)->data) return false;
if(flag ==0 && (rt->right)->data >= val) return false;

}

return (isBST(rt->left,rt->data,0) && isBST(rt->right,rt->data,1));
}

- ashish December 03, 2010 | Flag Reply