CareerCup

O(n^2) approach will be Top down approach

Int MaxBST(node *root)
{
if(!root)
return 1;

if(IsBst(root)) //
return Size(root);

else
return Max(MaxBST(root->left),MaxBST(root->right));

}

The second approach will be O(n) bottom UP
/*
root is the root of tree
min minimum value of tree rooted at root
max max value of tree rooted at root
p assign the value root which contains largest bst
return maxm no of largest BST
or return -1 if tree rooted at root is not BST
*/
Int LargestBST(node *root,int &min,int &max,int &maxnoofnodes, Node **p)
{
if(!root)
return 0;

bool Isbst=true;

int leftnodes = LargestBST(root->left,min,max,maxnoofnodes,&p)

int currmin = (leftnodes==0) ? root->data : min

if(leftnodes == -1 || (leftNodes != 0 && root->data < max))
Isbst = false;


int rightnodes=LargestBST(root->right,min,max,maxnoofnodes,&p)

int currmax= (rightnodes==0) ? root->data : max

if(rightnodes==-1 || (leftNodes != 0 && root->data > min))
Isbst=false;

if(Isbst)
{
min=currmin;
max=currmax;
int total=leftnodes+rightnodes+1;
if(total > maxnoofnodes){
maxnoofnodes=total;
p=root;}
return Maxnoofnodes;
}
else
return -1;
}

What if we do an inorder traversal and then find the largest increasing sequence. The length of this sequence will be the biggest BST of that Binary Tree.
Space O(n)
Time: O(n) + O(n)

1. We can find the longest sequentially increasing sub-sequence of the inorder traversal of the tree. O(n)
2. No we need to find the max value in this array - which is going to be the last element and also find the min element - which is going to be the first element. O(1)
3. We now find the least common ancestor of these two elements O(n). Call it root.
4. There after we call printAllAncestors(root.left) and printAllAncestors(root.right). O(n).


The complexity is O(n) for the algo.
Thanks.