CareerCup

see prev threads ..solution using INT_MAX AND INT_MIN

make a inorder traversal of a given tree and if the traversal is in sorted form then the given tree is BST.
10
/ \
5 15
/\ /\
3 8 13 18

Inorder: 3,5,8,10,13,15,18

output will always be sorted for inorder traversal of BST

struct node {
node *left;
node * right;
int data;
};
bool inorder(node * root) {
  static bool isBST = 1;
  static int count = 0;
  if(root) {
    inorder(root->left);
    chk_BST(root,isBST);
    count++;
    inorder(root->right);
  }
  else{
   cout<<"No. of nodes = "<<count;
   return isBST;
  }
}

chk_BST(node * root,bool isBST) {
   if(root->left) {
     if(root->data<root->left->data) {
       isBST = 0;
     }
   }
   if(root->right) {
     if(root->data>root->right->data) {
       isBST = 0;
     }
   }
}

Perform an inorder traversal of the tree and print all the node data. If the node data is in ascending order then it is a binary search tree. To count the number of nodes, keep a counter while traversing the tree inorder.

Detailed description for the above problem with two possible solutions is described here

crackinterviewtoday.wordpress.com/2010/03/12/check-whether-given-binary-tree-is-a-bst-or-not/

Using INT_MAX and INT_MIN only applicable if BST hold ints as data. If BST has elements that do not have natural ordering or, if they do, do not have min and max values (eg. strings), in-order traversal may work better (assuming BST elements have ordering/are comparable) save for the extra space requirement

template<typename T>
class TreeNode
{
public:
    TreeNode() {};
    ~TreeNode() {};

    TreeNode* left;
    TreeNode* right;

    T data;
};

template<typename T>
bool isBST(TreeNode<T>* root)
{
    static int count = 0;
    static bool bIsBST = true;    
    static TreeNode<T>* pLastVisited = NULL;

    if (root)
    {
        isBST(root->left);

        cout++;
        if (pLastVisited && pLastVisited->data > root->data)
            bIsBST = false;
        pLastVisited = root;

        isBST(root->right);
    }
     
    return bIsBST;
}

bool isBST(node * root) {
  bool isbst = true;
  isbst &= root->left ? isBST(root->left) & (root->left->value < root->value):true;
  isbst &= root->right ? isBST(root->right) & (root->right->value > root->value):true;  
  return isbst;  
}

int TreeCount = 0;
bool IsBST(TreeNode root)
{
return (NULL == root) ? true:
(TreeCount++ , (!root->left || (root->left->info <= root->info)) &&
(!root->right || (root->right->info <= root->info)) &&
IsBST(root->left) &&
IsBST(root->right));
}

int inorder(struct node *cur, struct node *prev)
{
int flag1, flag2;
if(cur==NULL) return 1;
flag1 = inorder(cur->left, prev);
if(prev==NULL) prev = cur;
else if(prev->data>cur->data) return 0;
flag2 = inorder(cur->right, cur);
return flag1 && flag2;
}

if(inorder(root, NULL)) print BST
else print not BST

Correction - Question is to find if a given binary tree is a binary search tree or not.

public bool IsItBinarySearchTree(Node node, int data)
{
bool status = true;
if (node != null)
{
if (data > node.data)
{
status = false;
}

if (node.left != null)
{
status = (node.left.data > node.data) ? false : true;
if (status)
{
status = IsItBinarySearchTree(node.left, node.left.data);
}
}

if (status && node.right != null)
{
status = IsItBinarySearchTree(node.right, node.data);
}
}

return status;
}

For invoking the above function, pass root & root.data

i.e. IsItBinarySearchTree(root, root.data);

Do inorder traversal. It should be sorted.

How about:

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);
}

isbinarysearch(node*root)
{
if(root==NULL)
return;
if(root->left)
{ if(root->left->data>root->data)
return false
}
if(root->right)
{
if(root->right->data<root->data)
return false
}
return true

isbinarysearch(node*root)
{
if(root==NULL)
return;
if(root->left)
{ if(root->left->data>root->data)
return false
}
if(root->right)
{
if(root->right->data<root->data)
return false
}
return true
isbinarysearch(root->left)
isbinarysearch(root->right)

bool isBST(Node *tree,int *nodeCount)
{
    if(tree)
    {
        bool result=true;
        
        if(tree->left==NULL && tree->right==NULL)
        {
            (*nodeCount)++;
            return true;
        }
        else
        {
            if(tree->left)
            {
                result=result && isBST(tree->left,nodeCount);
            }
            
            if(tree->right)
            {
                result=result && isBST(tree->right,nodeCount);
            }
            
            result=result && (tree->left && tree->left->value < tree->value) && (tree->right && tree->right->value >= tree->value);
        
            *nodeCount++;
            return result;
        }
    }
    else
        return false;
}

Just Inorder traverse the tree and determine the preNode < currentNode is fine
PNode IsBSTCore(PTree tree, PNode &pPreNode)
{
if(tree)
{
PNode pNode = IsBSTCore(tree->left, pPreNode);
if(pNode) return pNode;
if(pPreNode && pPreNode->data > tree->data)
{
return tree;
}
printf("%d\t%d\t", pPreNode? pPreNode->data : -1, tree->data);
pPreNode = tree;
pNode = IsBSTCore(tree->right, pPreNode);
return pNode;
}
return tree;
}
PNode IsBST(PTree tree)
{
assert(tree != NULL);
PNode pNode = NULL;
return IsBSTCore(tree, pNode);
}

this will return that binary tree is bst or not and also the no of nodes in the binary tree

int checkBST(struct node *r,int *count)
{
if(r==NULL)
return 1;
count++;
if(r->left && r->left->data>r->data)
k=0;
if(r->right && r->right->data<r->data)
k=0;
return(k && checkBST(r->left)&&chackBST(r->right));
}