C++ find largest BST in a binary tree

Posted by fonjibe on Stack Overflow See other posts from Stack Overflow or by fonjibe
Published on 2012-10-07T09:33:18Z Indexed on 2012/10/07 9:37 UTC
Read the original article Hit count: 253

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

© Stack Overflow or respective owner

Related posts about c++

Related posts about algorithm