CareerCup

// for each node check if node value mode than MIN and less than MAX
int max = INT_MAX;
int min = INT_MIN;

bool isBST(Node node, int min, int max)
{
    if (node.value > min && node.value < max)
    {
        return true && isBST(node.left, min, node.value) && isBST(node.right, node.value, max);
    }
    else
    {
         return false;
    }
}

bool isBST (Node *rootNodePtr) {
if (!rootNodePtr) {
    return true;
}

if ((rootNodePtr->left && rootNodePtr->key <= rootNodePtr->left->key) ||
    (rootNodePtr->right && rootNodePtr->key >= rootNodePtr->right->key)) {
    return false;
}

    return isBST (rootNodePtr->left) && isBST (rootNodePtr->right);
}

Don't think so, say if root is 5, root.left = 3, root.left.right is 1 and root.left.left is 6. The method will return true. I think we should in-order traversal and ensure that it visit node in monotonic increasing order.

@nugarp:

I figured we had a BST that didn't allow duplicate keys. Think we would have a little trouble finding a node with a given key if we allowed multiple nodes to have the same key.

@Salmok:

The code is correct as it is. We could also do it your way.

@nugarp:

So I guess we should have that check in both the if clauses. If either of the child has a key equal to it's parent, then it's also a violation of the BST constraint. Thanks.

/**
	 * Wrapper function
	 */
	public static boolean isBST(BSTNode root){
		Integer temp = new Integer(-1);
		return isBSTImpl(root,temp);
	}
	/**
	 * Real implementation
	 */
	private static boolean isBSTImpl(BSTNode r_, Integer pivot){
		//base case
		if(r_.left == null && r_.right == null){
			if(r_.value.intValue() < pivot.intValue()) 
				return false;
			else{
				pivot = r_.value;
				return true;
			}
		}else{
			boolean isBST = true;
			//left
			if(r_.left != null){
				isBST = isBSTImpl(r_.left, pivot);
			}
			//itself
			if(!isBST){
				return false;
			}else {
				if(r_.value.intValue() < pivot.intValue())
					return false;
				else
					pivot = r_.value;
			}
			//right
			return isBSTImpl(r_.right,pivot);
		}
	}

@Salmok:

I see your point now. My code is complete garbage. So inorder traversal seems to be a safe bet for this problem. Thanks.

Code in Java:

private void InOrderQueue(Queue<T> q) {
		if (left != null)
			left.InOrderQueue(q);
		q.add(data);
		if (right != null)
			right.InOrderQueue(q);
	}
	
	public boolean isBST() {
		T old = null;
		T _new = null;
		Queue<T> queue = new LinkedList<T>();
		InOrderQueue(queue);
		if (!queue.isEmpty())
			old = queue.poll();
		while (!queue.isEmpty()) {
			_new = queue.poll();
			if (_new.compareTo(old) < 0)
				return false;
			old = _new;
		}
		return true;
	}

Non-Recursive function in Java (e.g. if you want to call it on another node)

public class Node<T extends Comparable<T>> {
	private Node<T> left = null;
	private Node<T> right = null;
	private T data = null;
	private boolean flagged = false;

...

	public void flag() {
		flagged = true;
	}
	
	public boolean isFlagged() {
		return (flagged);
	}

	public void unflag() {
		if (left != null)
			left.unflag();
		flagged = false;
		if (right != null)
			right.unflag();
	}
	
	public boolean isBST(Node<T> t) {
		T old = null;
		T _new = null;
		Node<T> temp = null;
		Queue<T> queue = new LinkedList<T>(); /* will store the list of sorted nodes */
		Stack<Node <T>> stack = new Stack<Node <T>>(); /* recursive stack */
		stack.push(t);
		while (!stack.isEmpty()) {
			temp = stack.pop();
			if (temp.getRight() != null) {
				stack.push(temp.getRight());
			}
			if (!temp.isFlagged())
				stack.push(temp);
			if (temp.getLeft() != null) {
				stack.push(temp.getLeft());
			}
			if (!temp.isFlagged() && (temp.getLeft() == null || temp.getLeft().isFlagged())) {
				queue.add(temp.getData());
				temp.flag();
			}
		}
		t.unflag(); /* unflags all nodes */
		if (!queue.isEmpty())
			old = queue.poll();
			System.out.println(old);
		while (!queue.isEmpty()) {
			_new = queue.poll();
			System.out.println(_new);
			if (_new.compareTo(old) < 0)
				return false;
			old = _new;
		}
		return true;		
	}
}

I see a simple solution, while u do inorder traversal of tree, check whether next element in traversal is greater than previous or not. this will save memory as well (no need to store inorder in an array etc.) since it will hav O(n) worst case. at ny point if next ele is less than previous one, then tree is not bst and just brk/return false.

This is my version. I wrote a wrapper function that catches an exception when the helper function realizes that we don't have a binary tree. Essentially its a in-order walk with comparison the head value.

public boolean isBst(Node head){
                try {
                        isBstHelper(head);
                } catch(NotBSTException e){
                        return false;
                }
                return true;
        }

        int isBstHelper(Node head){
                if (head.left == null && head.right == null)
                        return head.value;

                if((head.left != null &&
                    isBstHelper(head.left) >= head.value) ||
                   (head.right != null &&
                    isBstHelper(head.right) < head.value))
                        throw new NotBSTException();
            
                return head.value;
        }

I guess that if you want to check whether the given tree is binary search tree or not, we can do INORDER traversal and print those elements.If the elements are in ascending order then we can say that the tree is a BST.In the following example given above its not a BST since the INORDER traversal is 1365789 in which 6>5.Hence its not a BST.

IsBST(node n){
return help(n,-maxint,maxint)
}

help(node n,int min,int max){
if(n.data<min || n.data>max)
return false
return help(n.left,min,n.data)&&help(n.right,n.data,max)
}

IsBST(node n){
return help(n,-maxint,maxint)
}

help(node n,int min,int max){
if(n is null)
return true
if(n.data<min || n.data>max)
return false
return help(n.left,min,n.data)&&help(n.right,n.data,max)
}

boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) {
if(node == null) {
return true;
}
if(node.value > min &&
node.value < max &&
IsValidBST(node.left, min, node.value) &&
IsValidBST(node.right, node.value, max)) {
return true;
}
else {
return false;
}
}

<pre lang="" line="1" title="CodeMonkey95843" class="run-this">public boolean isBST(Node localRoot){

if(localRoot.leftChild!=null){
if(localRoot.leftChild.key < localRoot.key)
return isBST(localRoot.leftChild);
else
return false;
}
if(localRoot.rightChild!=null){
if(localRoot.rightChild.key > localRoot.key)
return isBST(localRoot.rightChild);
else
return false;
}
return true;
}</pre><pre title="CodeMonkey95843" input="yes">
Seems simple. </pre>