CareerCup

Binary search trees have the property that the inorder traversal of the tree is a sorted array. The reciprocal of this property is also true.

So the easiest algorithm would be:
1. array a = inorder-traversal(tree)
2. check if a is sorted increasingly

Of course, you can merge those two steps into one and not use the additional array.

int isThisABST(struct node* mynode) {
if (mynode==NULL) return(true);
if (node->left!=NULL && maxValue(mynode->left) > mynode->data) return(false);
if (node->right!=NULL && minValue(mynode->right) <= mynode->data) return(false);
if (!isThisABST(node->left) || !isThisABST(node->right)) return(false);
return(true);
}

boolean isBinary (int isLeft, int value, Node node) {
if (!node)
return true;

if (isLeft && (value < node.value)) return false;
if (!isLeft && (value > node.value)) return false;

return (isBinary (1, node.value, node.left) && isBinary (0, node.value, node.right));
}


/* wrapper */
boolean isBinaryTree (Node root) {
if (!root)
return true;

int value = root.value;
return (isBinary (1, value, root.left) && isBinary (0, value, root.right));
}

O(N) complexity - preorder traversal

just reorder the tree by "in order" tree traversal and during reordering check if current value is greater or smaller than the previous value. as soon as you get it false, terminate the process and return false. in the worst case, runtime will be o(n)

For a given node n, call its closest parent N a "left parent" if n is on the right subtree of N, or call it "right parent" if n is on the left subtree of N.

ex:
k
\
m
/
n
for n, m is right parent, k is left parent.

for a given node n, left parent L and right parent R
function(Node n, bool isLeftChild, Node Lparent, Node Rparent)
{
if isleftChild
check if n < Rparent
check if n > Lparent
else
check if n > Lparent
check if n < R parent
function(n.left, true, Lparent, n)
function(n, n.right, n, Rparent)
}

and run it with :
function(root.left, true, null, root)
function(root.right, false, root, null)

// pushes the node n and the left children of it on to the stack recursively
void PushLeft(Stack stack, Node node)
{
	if (node == null)
		return
	stack.Push(node);
	PushLeft(stack, node.left);
}

// pops from stack, compares with previous value
// and calls PushLeft on right child.
// this method pops tree nodes from stack in an ascending order.
bool IsBST(Stack stack, Node previousNode)
{
	while(stack.IsEmpty == false)
	{
		Node node = stack.Pop();
		if (previousNode != null && node < previousNode)
			return false;
		previousNode = node;
		PushLeft(stack, node.right);
	}
	return true;
}

void Main()
{
	Stack s = new Stack();
	PushLeft(s, root);
	IsBST(s, null)
}

public boolean isBST() {
		return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	
	private boolean isBST(Node n, int min, int max) {
		if(n == null)
			return true;
		
		if(n.data < min | n.data > max)
			return false;
		
		return isBST(n.left, min, n.data) && isBST(n.right, n.data, max);
	}

easies way to do is to do a in place traversal and then see if the output is a sorted list from Min to Max

Don't you have to check first if the tree is a binary tree.. and then check if it's a BST? Maybe the tree isn't binary tree.

bool
isBinary (Node* node)
{
	if (n == 0)
	{
		return false;
	}

	if (n->left != 0)
	{
		if (n->value > n->left->value)
		{
			return (isBinary (n->left));
		}
		else
		{
			return false;
		}
	}

	if (n->right != 0)
	{
		if (n->value < n->right->value)
		{
			return (isBinary (n->right));
		}
		else
		{
			return false;
		}
	}

	return true;
}

isBST( root ) {
    if ( root == null )
        return true;
    if ( root.left != null && root.left.data > root.data )
        return false;
    if ( root.right != null && root.right.data < root.data )
        return false;
    return isBST(root.left) && isBST(root.right);
}