C++ find largest BST in a binary tree

Question

what is your approach to have the largest BST in a binary tree? with largest, i mean: highest.

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)
{ 
      return includeSomeBST(n->left)  ||  includeSomeBST(n->right) ;

      if(n == NULL)
           return false ; 

      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

What is the largest BST? Are you looking for the height of the tree? Or its deepest node? Your question is quite unclear. — avakar, Oct 07 '12 at 09:48

score 1 · Accepted Answer · answered Oct 07 '12 at 10:30

1

Yes,your function includeSomeBST is wrong. You just check the nodes n,n->left and n->right, but you must check the nodes recursively.

bool includeSomeBST(BinaryTree* n) {

  if(!isBinarySearchTree(n))
  {

       return includeSomeBST(n->left) || includeSomeBST(n->right);
  }

  if(n==NULL) return false; 
  return true;

}

answered Oct 07 '12 at 10:30

dingding qian

36
2

some idea on the largest tree problem? – kiriloff Oct 07 '12 at 11:39
@fonjibe As you said,the largest tree problem is the hightest tree problem.One possible easy solution is: 1, for every node,add an element "level" representing the height.The height of leaf node is zero,and you can calculate others nodes' height recursively. 2, for every node,add an element "is_bst", you can use the function isBinarySearchTree to calculate this value for every node recursively. 3, find the node which has the biggest level and which is bst recursively – dingding qian Oct 07 '12 at 12:24

score 0 · Answer 2 · answered Oct 08 '12 at 18:37

Here is a successful code implementation for the same along with the driver program:

#include <iostream>
using namespace std;

class BinaryTree {
    public:
        BinaryTree *right;
        BinaryTree *left;
        int value;
        BinaryTree(int value) {
            this->value = value;
        }
};


int max_value(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int min_value(int a, int b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

BinaryTree* findLargestBST(BinaryTree *n, int* maxSize, int *max, int *min, bool *is_bst) {
    if (n == NULL) {
        *maxSize = 0;
        *is_bst = true;
        return n;
    }
    int *lc_max_size = new int;
    int *rc_max_size = new int;
    int *lc_max = new int;
    int *lc_min = new int;
    int *rc_max = new int;
    int *rc_min = new int;
    *lc_max = std::numeric_limits<int>::min();
    *rc_max = *lc_max;
    *lc_min = std::numeric_limits<int>::max();
    *rc_min = *lc_min;
    BinaryTree* returnPointer;

    bool is_curr_bst = true;
    BinaryTree* lc = findLargestBST(n->left, lc_max_size, lc_max, lc_min, is_bst);
    if (!*is_bst) {
        is_curr_bst = false;
    }

    BinaryTree* rc = findLargestBST(n->right, rc_max_size, rc_max, rc_min, is_bst);
    if (!*is_bst) {
        is_curr_bst = false; 
    }

    if (is_curr_bst && *lc_max <= n->value && n->value <= *rc_min) {
        *is_bst = true;
        *maxSize = 1 + *lc_max_size + *rc_max_size;
        returnPointer = n;
        *max = max_value (n->value, *rc_max);
        *min = min_value (n->value, *lc_min);
    } else {
        *is_bst = false;
        *maxSize = max_value(*lc_max_size, *rc_max_size);
        if (*maxSize == *lc_max_size) {
            returnPointer = lc;
        } else {
            returnPointer = rc;
        }
        *max = *min = n->value;
    }

    delete lc_max_size;
    delete rc_max_size;
    delete lc_max;
    delete lc_min;
    delete rc_max;
    delete rc_min;
    return returnPointer;
}

int main() {

    /* Let us construct the following Tree
          50
       /      \
     10        60
    /  \       /  \
   5   20    55    70
            /     /  \
          45     65    80
  */

  BinaryTree *root = new BinaryTree(50);
  root->left        = new BinaryTree(10);
  root->right       = new BinaryTree(60);
  root->left->left  = new BinaryTree(5);
  root->left->right = new BinaryTree(20);
  root->right->left  = new BinaryTree(55);
  root->right->left->left  = new BinaryTree(45);
  root->right->right = new BinaryTree(70);
  root->right->right->left = new BinaryTree(65);
  root->right->right->right = new BinaryTree(80);

  /* The complete tree is not BST as 45 is in right subtree of 50.
     The following subtree is the largest BST
        60
      /  \
    55    70
   /     /  \
  5     65    80
  */

  int *maxSize = new int;
  int *min_value = new int;
  int *max_value = new int;
  *min_value = std::numeric_limits<int>::max();
  *max_value = std::numeric_limits<int>::min();
  bool *is_bst = new bool;
  BinaryTree *largestBSTNode = findLargestBST(root, maxSize, max_value, min_value, is_bst);
  printf(" Size of the largest BST is %d", *maxSize);
  printf("Max size node is %d", largestBSTNode->value);
  delete maxSize;
  delete min_value;
  delete max_value;
  delete is_bst;
  getchar();

  return 0;
}

The approach used is fairly straightforward and can be understood as follows:

It is a bottom to top approach instead of a top to bottom one which we use when determining whether the tree is a BST or not. It uses the same max-min approach used while determining the tree as a BST or not.

Following are the steps which are executed at each of the nodes in a recursive fashion: Note: Please remember that this is a bottom up approach and the information is going to flow from the bottom to the top.

1) Determine whether I am existent or not. If I am not (I am null) I should not influence the algorithm in any way and should return without doing any modifications.

2) At every node, maximum size of the BST till this point is stored. This is determined using the total size of the left subtree + the total size of the right subtree + 1(for the node itself) if the tree at this particular node satisfies the BST property. Otherwise, it is figured out from the max values that have been returned from the left subtree and the right subtree.

3) In the case if the BST property is satisfied at the given node then the current node is returned as the maximum size BST till this point otherwise it is determined from the left and the right subtrees.

C++ find largest BST in a binary tree

2 Answers2