Thread: Largest Binary Search Tree in a given Binary Tree

Find Largest Binary Search Tree in a given Binary Tree.

Traverse the tree. From each node to the parent, return the following
set of values.

1) If BST, size of the current BST or -1 if the tree is not.
2) Minval & Maxval of the subtree and maxbstsize seen so far (
probably using references)

So in each node check the following:

If( leftmax < node->data && node->data < rightmin) // Means it is a BST
{
new size = rightsize+leftsize+1
update size if greater than max
return size
}
else
{
return -1;
}

Code:

#include <stdlib.h>
#include <stdio.h>
using namespace std;

struct node
{
  int data;
  struct node* left;
  struct node* right;
};

struct node* insert_bst(struct node* root, int num){
  if(root == NULL){
    root = (struct node*)malloc(sizeof(struct node));
    root->data = num;
    root->left = NULL;
    root->right = NULL;
    return root;
  }else{
    if(num == root->data){
      return root;
    }

    if(num > root->data){
      root->right=insert_bst(root->right,num);
    }else{
      root->left=insert_bst(root->left,num);
    }
  }
  return root;
}

void inorder_traverse(struct node* root){
  if(root == NULL) return;

  inorder_traverse(root->left);
  printf("%d ",root->data);
  inorder_traverse(root->right);
}

struct node* bst_root = NULL;

int getmaxbst(struct node* root, int& subtreemin, int &subtreemax, int& max)
{
  if(root == NULL) return 0;

  int leftsubtreemin = -32767, rightsubtreemin = -32767;
  int leftsubtreemax = 32767, rightsubtreemax = 32767;
  int x,y;

  x = getmaxbst(root->left, leftsubtreemin, leftsubtreemax, max);
  y = getmaxbst(root->right, rightsubtreemin, rightsubtreemax, max);

  if(x==-1 || y ==-1)
    return -1;
  if(x==0) { leftsubtreemax = root->data; leftsubtreemin = root->data;}
  if(y==0) { rightsubtreemin = root->data; rightsubtreemax = root->data;}

  if(root->data < leftsubtreemax ||
     root->data > rightsubtreemin){
    return -1;
  }

  subtreemin = leftsubtreemin;
  subtreemax = rightsubtreemax;

  if(x+y+1 > max){
    max = x+y+1;
    bst_root = root;
  }

  return x+y+1;

}

int main()
{
  struct node* root=NULL;

  root=insert_bst(root,5);
  root=insert_bst(root,3);
  root=insert_bst(root,9);
  root=insert_bst(root,7);
  root=insert_bst(root,4);
  root=insert_bst(root,1);
  root=insert_bst(root,14);
  root=insert_bst(root,11);

  root->data = 0;

  int a,b,c,max=-32767;
  c = getmaxbst(root,a,b,max);
  printf("\nmax is %d\n",max);

  inorder_traverse(bst_root);
  return 1;
}