CareerCup

It can be done as follows:

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

You can use same normal BST verification with min and max but at each recursive call, need to check if root->data is not same as left or right data.

You can use same normal BST verification with min and max but at each recursive call, need to check if root->data is not same as left or right data.

Can be done with two traversal:

First traversal:
Find if any in-order successor of any node is equal to that node to find our duplicate
Second traversal:
Do post order traversal, and each traversal get (min, max) from both subtree and then check for BST property.

"need to check if root->data is not same as left or right data"
why this check is required at all?
can't we simply go with min/max ..that itself insures that there is no element in left subtree less than or equal to it and similar in right subtree

modify the inorder traversal and at each recursive call instead of printing the root, add the root.key into a array with constraint that this root.key> array[lastIndex].

Do in-order traversal, items will be in order if BST (if previous items is larger than next, not a BST) and you can check for duplicate by comparing the last item with the next item

One traversal O(n)

1) Insert the elements of the tree in to an array doing an inorder traversal
2) Check if the array is sorted and doesnt contain duplicates.

We can find the inorder traversal of the tree and check if the data in every left node is less than (not less than or equal to) to the data in it's right node. If it is a BST then the duplicate elements will be consecutive in the inorder traversal.
This is a very simple slution. The inorder traversal can be done either using recursion or the iterative method.