CareerCup

yes why cant we just do an in order traversal and check if the resulting string is sorted??

IsBinarySearchTree(Node root)
{
if(root == null) return false

IsBinarySearchTree(node.Left) && IsBinarySearchTree(node.Right)

if(node.Right != null && node.Left !=null)
{
return (node.Right.Data > Node.Data && node.Left.Data < node.Data)
}
else if ( node.Right == null)
{
return (node.Left.Data < node.Data)

} else
{
return (node.Right.Data > node.Data)

}
}

compute inorder of the tree,
if it is sorted then its a BST

boolean isBinarySearchTree(Node root){
if(root==null) return true; //assume empty node is a binary search tree
else{
if(root.left!=null)
if(root.data<=root.left.data)
return false;
if(root.right!=null)
if(root.data>=root.right.data)
return false;
}
return isBinarySearchTree(root.left)& isBinarySearchTree(root.right);
}

I'm not sure. But shouldn't we check both the lower bound and upper bound of a specific tree node?

<pre lang="java" line="1" title="CodeMonkey29109" class="run-this">boolean isBinarySearchTree(Node r){
if(r.isLeaf){
return true;
}
if(r.key>=r.left.key && r.key<r.right.key){
return (true && isBinaryTree(r.left) && isBinaryTree(r.right))
}
else{
return false;
}
}</pre><pre title="CodeMonkey29109" input="yes">
</pre>

Start At root:
For each node in BST : minData < node.data < maxData
For root : minData = Negative Infinity maxData = Positive Infinity
For root.left : minData = Negative Infinity maxData = root.data
For root.right : minData = root.data maxData = Positive Infinity

Recurse till u find a node where BST condition is violated or node is null.

public class BSTChecker {

public static void main(String[] args) {
Node root = new Node(5);
Node l1 = new Node(4);
Node r1 = new Node(6);
root.left = l1;
root.right = r1;
Node l1L = new Node(3);
Node l1R = new Node(5);
l1.left = l1L;
l1.right = l1R;
System.out.println(isBST(root));
}

static class Node {
int data;
Node left;
Node right;

public Node(int data) {
this(data, null, null);
}

public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}

public static boolean isBST(Node root) {
return isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE);
}

private static boolean isBST(Node node, int maxValue, int minValue) {
if (node == null) {
return true;
} else if (node.data > maxValue || node.data < minValue) {
return false;
} else {
return isBST(node.left, node.data, minValue)
&& isBST(node.right, maxValue, node.data);
}
}
}

bool validate(bst *node)
{
	if(node)
	{
		if(validate(node->left)) 
		{
			if(node->left) 
			{
				if(node->left->data < node->data)
				{
					if(validate(node->right)
					{
						if(node->right)
						{
							if(node->right->data > node->data)
								return TRUE;
							return FALSE;
						}
						return TRUE;
					}
					return FALSE;
				}
				return FALSE;
			}
			else
			{
				if(validate(node->right)
				{
					if(node->right)
					{
						if(node->right->data > node->data)
							return TRUE;
						return FALSE;
					}
					return TRUE;
				}
				return FALSE;
			}
		}
		return FALSE;
	}
	return TRUE;
}

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0


typedef int bool;
typedef struct bst{
struct bst *left;
struct bst *right;
int data;
}bst;

bst * newNode(int data);
bool validate(bst *node, int MIN, int MAX);

int main(int argc, char **argv)
{
  bst *node;
  node = newNode(40);
  node->left        = newNode(20);
  node->right       = newNode(60);
  node->left->left  = newNode(10);
  node->left->right = newNode(30);
  node->right->left = newNode(35);


  if(validate(node,node->data,node->data))
    printf("Is BST\n");
  else
    printf("Not a BST\n");
    
  return 0;

}

bst * newNode(int data)
{
  bst *node = (bst *)malloc(sizeof(bst));
  if(!node)
  	return NULL;

  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return node;
}

bool validate(bst *node, int MIN, int MAX) 
{
     if(node)
     {
		   if(node->data >= MIN && node->data <= MAX && validate(node->left,MIN,node->data) && validate(node->right,node->data,MAX))
		       return TRUE; 
		   return FALSE;
     }
     return TRUE;
}

boolean isBST(Node n, int lower, int upper){
if(n == null)
return true;

if(n > upper || n < lower)
return false;

return isBST(n.left, lower, n.value) && isBST(n.right, n.value, upper);
}