C++ find largest BST in a binary tree
- by fonjibe
what is your approach to have the largest BST in a binary tree?
I refer to this post where a very good implementation for finding if a tree is
BST or not is
bool isBinarySearchTree(BinaryTree * n,
int min=std::numeric_limits<int>::min(),
int max=std::numeric_limits<int>::max())
{
return !n || (min < n->value && n->value < max
&& isBinarySearchTree(n->l, min, n->value)
&& isBinarySearchTree(n->r, n->value, max));
}
It is quite easy to implement a solution to find whether a tree contains a binary search tree. i think that the following method makes it:
bool includeSomeBST(BinaryTree* n)
{
if(!isBinarySearchTree(n))
{
if(!isBinarySearchTree(n->left))
return isBinarySearchTree(n->right);
}
else
return true;
else
return true;
}
but what if i want the largest BST? this is my first idea,
BinaryTree largestBST(BinaryTree* n)
{
if(isBinarySearchTree(n))
return n;
if(!isBinarySearchTree(n->left))
{
if(!isBinarySearchTree(n->right))
if(includeSomeBST(n->right))
return largestBST(n->right);
else if(includeSomeBST(n->left))
return largestBST(n->left);
else
return NULL;
else
return n->right;
}
else
return n->left;
}
but its not telling the largest actually. i struggle to make the comparison. how should it take place?
thanks
