Very Faq. Asked Question All Tech Giants :) Will Post The Solution Soon :) Meanwhile You Can Try & Post the approach .
Prerequisite : Most Efficient Solution to Check if Given Tree is BST or not ? !st Try it or Search Archives :)
Basic Idea :
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:
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;
}
Working Code:
/* Largest Binary search tree inside a binary tree -- O(n)*/
#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;
}
TC O(N)
SC O(1)
