CareerCup

Do inorder traversal.if outcome is sorted than it is a bst.

This is the correct solution. Found it in geeksforgeeks.org.

int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its
values are >= min and <= max. */
int isBSTUtil(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;

/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}

Here is my implementation:

basicalgos.blogspot.com/2012/03/25-binary-search-tree-verification.html

The above implementation requires O(N) space complexity. Can we solve it with less space?

bool inorder(node *root)
{
if(!root)
return true;

static node *prev=NULL;

Inorder(root->left);

//if it is not sorted
if(prev!=NULL && root->data < prev->data)
return false;

prev=root;

Inorder(root->right);

}

int Is_BST ( node* root ) {

if ( root == NULL ) return 1;

if ( root.Key > root.Right.Key ) return 0;
if ( root.Key < root.Left.Key ) return 0;

return ( Is_BST(root.Right) && Is_BST(root.Left));


}

I give two solutions with same time and space complexity:
The first solution uses the feature of numbers being sorted in in-order traversing. The signature is like "bool IsBST(Node root, ref int lastValue)" in C#.
1. if root is null then return true;
2. if IsBST(root.lchild, ref lastValue) is false then return false. (It means that the left sub-tree of root is not BST)
3. if lastValue >= root.value then return false. (It means that the root is smaller than the biggest value in its left sub-tree)
4. lastValue=root.value
5. return IsBST(root.rchild, ref lastValue)
This solution is used like :
int lastValue=int.MinValue;
IsBST(root, lastValue);


The second solution uses the boundary feature of BST. The signature of method is like "bool IsBST(Node root, int min, int max)" in C#
1. if root is null then return true.
2. return (root.value>min&&root.value<max)&&IsBST(root.lchild, min, root.value)&&IsBST(root.rchild,root.value,max)
This solution is used like:
IsBST(root, int.MinValue, int.MaxValue);

Do Inorder traversal ( either using recursion or iterative version ) ..
the element that you first print store it in prev .
from next time onwards , the element that you are supposed to print in inorder traversal , you make sure that as curr , and compare curr with prev , to make sure that curr > prev .
now replace your prev with curr .
at any point of time if curr < prev then it is not a BST , otherwise it is .