CareerCup

Perform an inorder traversal, it should result in an increasing order of elements!

public boolean isBST(TreeNode root, int min,int max)
{
   if(root==null)
      return true;
   if(root.value<min||root.value>max)
      return false;
   return isBST(root.left,min,root.value)&&isBST(root.right,root.value,max)
}

First call will be isBST(root,INT.min,INT.max);

There are 3 solutions using DFS, BFS, and Morris traversal to detect a binary tree is a BST or not at the entry "Does a binary tree satisfy the BST property?" of code.google.com/p/elements-of-programming-interviews/wiki/Programs

It is the solutions of another programming interviews book titled "Elements of Programming Interviews: 300 Questions and Solutions"

4 lines with recursion. i hope i'm not missing something here.. this should work

public boolean isBST(Node n){
    if(n == null || ((n.right == null) && (n.left == null))) return true; //child node or base case
    if((n.left == null || n.right == null) && (n.left.value > n.value || n.right.value < n.value) return false; //unbalanced tree
    if(n.left.value > n.right.value) return false;// not correct bst
    return isBST(n.left) && isBST(n.right); //check all nodes
}

{{
struct node
{
int data;
struct node *next;
}*start;


void Check_Bst(node root)
{
Check_Bst(root->left);
linkedlist(root);
Check_Bst(root->right);
}


void linkedlist(node root)
{
struct node *new , temp;
new =(struct node*)malloc(sizeof(struct node));
new->data = root->data;
new->next=NULL;
if(start ==NULL)
start=new;
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new;
}

}

void display(struct node *root)
{
struct node *flow;
flow=root->next;
if(root==NULL)return 0;
else
{
while(root!=NULL)
{
if(flow->data >root->data)
{
root=flow;
flow=flow->next;
}
else
{
flag=0;
break;
}
}
}
if(flag==0)
printf("not BST");
}
void main()
{
Check_Bst(root);
display(root);
}

}}

Do inorder traversal. Check if the traversed sequence is sorted or not.

Why not Level order Traversal?
Refer :
www[dot]geeksforgeeks[dot]org/level-order-tree-traversal/

Little modification needed as below :

boolean isBST(root) {
int rear, front;
struct node **queue = createQueue(&front, &rear);
struct node *temp_node = root;
while(temp_node) {
//printf("%d ", temp_node->data);

/*Enqueue left child */
if(temp_node->left && temp_node->left < data) {
enQueue(queue, &rear, temp_node->left);
} else {
return false ;
}

/*Enqueue right child */
if(temp_node->right && temp_node->right->data > data ) {
enQueue(queue, &rear, temp_node->right);
} else {
return false ;
}
/*Dequeue node and make it temp_node*/
temp_node = deQueue(queue, &front);
}
//All the nodes are passed
return true;
}

inorder traveling require O(n) space, here is O(1) space with same time complexity algorithm
start recursion from root node, in recursion visit all nodes,
during back tracing start verifying from leaf node.
if at all places we get yes, then it is BST, other wise not.

1.) Do inorder traversal of the tree
2.)check whethr the obtained list is in Ascending or Descending Order as per requirement

;)

Given that TreeNode has a left and right nodes and a payload that implements Comparable.

public boolean checkBST(TreeNode<T> root) {

        if(root==null) return true;

        T payload = root.getPayload();

        if ((root.left!=null && root.left.getPayload().compareTo(payload)>0) || (root.right!=null && root.right.getPayload().compareTo(payload)<0)) {
            return false;
        } else {
            return checkBST(root.left) && checkBST(root.right);
        }
    }

{That being a BST, the value in the node should obey the rules.
boolean checkBST(Node n, int min, int max){
if(n == null) return true;
if(n.data > max || n.data < min) return false;
return checkBST(n.left, min, n.data) && checkBST(n.right, n.data, max);
}
}

int is_bst(node *root)
{
int i,j,k=0,l=0;
if(root == NULL )
{
return 1;
}
if(root->left==NULL||root->left->value<root->value)
k=1;
if(root->right==NULL||root->right->value>root->value)
l=1;
i=is_bst(root->left);
j=is_bst(root->right);
if(i&&j&&k&&l)
return 1;
else
return 0;

}

boolean isBST(TreeNode node) {
    if (node == null) return true;
    isBST(node.left);
    isBST(node.right);
    return (node.left==null?true:node.data > node.left.data) 
           && 
           (node.right==null?true:node.data < node.right.data);
}

public boolean isBST(Node n) {
	if(n == null) {
		return true;	
	}

	bool left = n.left == null || (n.left.value < n.value && isBST(n.left));
	bool right = n.right == null || (n.right.value >= n.value && isBST(n.right));

	return left && right;
}

I'm not very sure, wasn't there a condition like, for a BST to be balanced, the height difference between levels should be 2 at most?

private bool Validate (Tree t)
{
if (t == null)
return true;
if (t.Left != null && t.Value < t.Left.Value)
return false;
if (t.Right != null && t.Value > t.Right.Value)
return false;
return Validate(t.Left) && Validate(t.Right);
}