CareerCup

traverse the tree in INorder , and count till the ascending order sorting order fails!

There can be two cases.
(1) One in which the subtree should completely be a BST.
(2) Other in which a part of subtree can be a BST.
So which one is being referred ?

(1)

bool findLargestBST(tree *root, int *c)
{
if(root == NULL)
{
return true;
}
int x = 0;
int y = 0;
bool p = findLargestBST(root->left, &x);
bool q = findLargestBST(root->right, &y);

if(root->left)
root->min = root->left->min;
else
root->min = root->data;

if(root->right)
root->max = root->right->max;
else
root->max = root->data;

if(p && q && (root->left == NULL || root->data > root->left->max) && (root->right == NULL || root->right->min > root->data))
{
*c = (x + y + 1);
return true;
}
*c = max(x, y);
return false;
}

Nice article on this (remove spaces)

ihas1337code . com/2010/11/largest-binary-search-tree-bst-in.html

Well I would outline a simple solution in this way:-
Have two variables, depth (integer) = 0 and largestBSTRoot (Reference/Ptr to Node class) = NULL.

1) Query each node whether it is a root of a BST. This means that both its left and right subtrees must be BSTs and left node must be larger than it and right node smaller. If it is a leaf node it is trivially a BST.

2) Whenever a node finds that it is a root of a BST, check if its height is larger than the value of "depth". If it is, replace largestBSTRoot with ptr/ref to node.

Time Complexity is O(n) as we are doing DFS, Space complexity is O(n) as well due to the bloody recursion.