CareerCup

leetcode . com / 2010 / 11 / largest-binary-search-tree-bst-in.html

We can divide the problem into several small problems:

1) For each node p, is the subtree with p as its root a binary search tree?
2) If it is a binary search tree, what is the size of the tree?

We can use recursion to do this:
Step1. for each node p, compute the minimum and maximum element of the subtree that rooted in p, as well as the size of the subtree.
Step 2. for each node p, check the maximum element of its left subtree and the minimum element of its right subtree to see if it is a BST, and if it is, sum up the size of the left right subtree and itself to get the size.
Step 3. Traversal the tree to find out the maximum BST as its subtree.

/* Its difficult to understand what's going on in the code -- 
It is a divide an conquer..
Where we find the largest subtree in left.
And largest subtree in right.
and if root satisfies the BST property .. 
Take max of (3,Union(root, left, right)) ..

Union means joining the subtree's to the root if their heads are the children.
Here is the algo
Traverse Post Order.
At each Node 
    Base case -- if leaf  ----- return 1;
If BST property is satisfied at this node then.. 
     Add set the value to 3;
     if left is positive add it and subtract 1.
     if right is positive add it and subtract 1.
     Take max of left, right and current value. and return that.
else 
     Take absolute of left and right values. Then take the max between them.
      return the negative of this number.

In the end return the absolute of this answer.

The code only gives the size of the max tree. but easily we can augment this code 
to find out the tree. by keeping track of the current max tree and discarding the other.

We will have to destroy the tree. Other wise it will take exponential space.
But since one node can be a part of only one such candidate tree. Time complexity still remains O(n).

I have not written that code. because of lack of time.

typedef struct SearchTree {
    int val;
    struct SearchTree *l;
    struct SearchTree *r;
} bst;


int largestBSTIn(bst *head) {
    int l = 0, r = 0, h = 0;
    if (head->l == NULL && head->r == NULL)
        return 1;
    if (head->l)
        l = largestBSTIn(head->l);
    if (head->r)
        r = largestBSTIn(head->r);
    cout << "\n" << head->val << " " << l << " " << r;
    if ((head->l == NULL || head->l->val < head->val) && ((head->r == NULL) || head->val < head->r->val)) {
        h = (l > 0) ? (h + l) : h;
        h = (r > 0) ? (h + r) : h;
        h++;
        if (l < 0) {
            h++;
            l = -l;
            h = (h > l) ? h : -l;
        }
        if (r < 0) {
            h++;
            r = -r;
            h = (h > r) ? h : -r;
        }
    } else {
        if (l < 0) l = -l;
        if (r < 0) r = -r;
        h = -(l > r ? l : r);
    }
    return h;
}
int largestBST(bst *head) {
    int ans = largestBSTIn(head);
    return (ans > 0 ? ans : (-ans));
}

The idea here is traverse tree in inorder fashion and count the node and update the tree if it is BST. Checking for BST and counting the node can be done in same recursion for in order. It happens in one scan of tree and time complexity is O(n).
Here is the code.

// root is the inorder successor of prev, however we set prev to null if left subtree is not BST or root is less than prev. 
int isBST(Node* root, int *node_count, Node* prev, Node *currmax, int* max_count){
	if( root == null) {*node_count = 0; return 1;}
	
	int *lc; // node counter for left subtree
	int *rc; // node counter for right subtree
	int lf; // flag to test if left subtree is BST 
	int rf; // flag to test if right subtree is BST 
	int mf; // flag to test if root of right sub tree is greater than root 
	// NOTE : root is BST if all the the three flags are set 
	
	lf = isBST( root->left, node_count, prev, currmax, max_count);
	if( !lf ) prev = null;
	mf = 1;
	if( prev != null  && prev->data > root->data ) {
		mf = 0; 
		prev = null; 
	}
			
	prev = root;
	rf = isBST(root->right, node_count, prev, currmax, max_count);
	
	int flag = lf && rf && mf; 
	if(flag){
		int count = *lc + *rc + 1;
		if( count > *max_count ){
			currmax = root;
			*max_count = count; 
		}
	}
	return flag;
}

main(){
	Node * root = constructTree() // function that creates a tree and return the root;
	int *node_count = 0;
	Node* prev = null;
	Node* currmax = null;
	int* max_count = 0;
	
	
	isBST(root, node_count, prev, currmax, max_count);

}

I posted the isBST function. Sorry, I passed a parameter node_count that is not even used and ignore that while going through code.

Can we do a inorder travelsal of the tree - return as an array and the longest sorted portion of the array would be the largest BST in the binary tree

bottom up recursion

int min,max,no,tempmin,tempmax,largestno=-1;
node largest;
int largest(node root){
if(root==null) return 0;

int l=largest(root.left);
if(l!=-1&&l!=0){ tempmin=min;if(root.data<=max) return -1;}
else if(l==0) tempmin=root.data;
else return -1;

int r=largest(root.right);
if(r!=-1&&r!=0){ tempmax=max;if(root.data>=min) return -1;}
else if(r==0) tempmax=root.data;
else return -1;

min=tempmin;
max=tempmax;
no=1+l+r;
if(no>largestno) largest=root;
return no;
}

if the subtree doesn't require containing all the subnodes

int no=0,max=-1;
node largest;
node largest(node root,int min,int max){
if(root==null){ no=0; return null;}

node l=largest(root.left,min,root.data);
node x=new node(root);
int tmp=no;
x.left=l;
x.right=largest(root.right,root.data,max);

if(root.data<max&&root.data>min){
no=tmp+no+1;
if(no>max) largest=x;
return x;}

no=0;
return null;
}

int maxCount = 0;
TreeNode1* maxTree = NULL;

int LargestBSTSubtree(TreeNode1* root)
{
	// If empty node, return 0
	if(!root)
		return 0;

	// find the largest BST in left tree
	int left =  LargestBSTSubtree(root->left);
	
	// find the largest BST in left tree
	int right =  LargestBSTSubtree(root->right);

	// if either child is not a BST, this can be a BST
	if(left==-1 || right==-1)
		return -1;

	// verify if current node, holds BST properties
	if((root->left) && root->left->val > root->val)
		return -1;

	if((root->right) && root->right->val < root->val)
		return -1;

	// if all good, check if this is the largest
	if(maxCount<left+right+1)
	{
		maxCount = left+right+1;
		maxTree = root;
	}

	// return size of this valid BST
	return left+right + 1;
}

/* Returns size of the largest BST subtree in a Binary Tree
  (efficient version). */
int largestBST(struct node* node)
{
  // Set the initial values for calling largestBSTUtil()
  int min = INT_MAX;  // For minimum value in right subtree
  int max = INT_MIN;  // For maximum value in left subtree
 
  int max_size = 0;  // For size of the largest BST
  bool is_bst = 0;
 
  largestBSTUtil(node, &min, &max, &max_size, &is_bst);
 
  return max_size;
}
 
/* largestBSTUtil() updates *max_size_ref for the size of the largest BST
   subtree.   Also, if the tree rooted with node is non-empty and a BST,
   then returns size of the tree. Otherwise returns 0.*/
int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,
                            int *max_size_ref, bool *is_bst_ref)
{
 
  /* Base Case */
  if (node == NULL)
  {
     *is_bst_ref = 1; // An empty tree is BST
     return 0;    // Size of the BST is 0
  }
 
  int min = INT_MAX;
 
  /* A flag variable for left subtree property
     i.e., max(root->left) < root->data */
  bool left_flag = false;
 
  /* A flag variable for right subtree property
     i.e., min(root->right) > root->data */
  bool right_flag = false;
 
  int ls, rs; // To store sizes of left and right subtrees
 
  /* Following tasks are done by recursive call for left subtree
    a) Get the maximum value in left subtree (Stored in *max_ref)
    b) Check whether Left Subtree is BST or not (Stored in *is_bst_ref)
    c) Get the size of maximum size BST in left subtree (updates *max_size) */
  *max_ref = INT_MIN;
  ls = largestBSTUtil(node->left, min_ref, max_ref, max_size_ref, is_bst_ref);
  if (*is_bst_ref == 1 && node->data > *max_ref)
     left_flag = true;
 
  /* Before updating *min_ref, store the min value in left subtree. So that we
     have the correct minimum value for this subtree */
  min = *min_ref;
 
  /* The following recursive call does similar (similar to left subtree)
    task for right subtree */
  *min_ref =  INT_MAX;
  rs = largestBSTUtil(node->right, min_ref, max_ref, max_size_ref, is_bst_ref);
  if (*is_bst_ref == 1 && node->data < *min_ref)
     right_flag = true;
 
  // Update min and max values for the parent recursive calls
  if (min < *min_ref)
     *min_ref = min;
  if (node->data < *min_ref) // For leaf nodes
     *min_ref = node->data;
  if (node->data > *max_ref)
     *max_ref = node->data;
 
  /* If both left and right subtrees are BST. And left and right
     subtree properties hold for this node, then this tree is BST.
     So return the size of this tree */
  if(left_flag && right_flag)
  {
     if (ls + rs + 1 > *max_size_ref)
         *max_size_ref = ls + rs + 1;
     return ls + rs + 1;
  }
  else
  {
    //Since this subtree is not BST, set is_bst flag for parent calls
     *is_bst_ref = 0;
     return 0;
  }
}

I think the following one is the optimum solution:

class TNode {
  public: //declare public for code simplicity
   int val;
  TNode *left, *right;
}

queue <TNode *> NQ;


int BST(TNode *r)
{
	if (r==NULL) return 0;
	if ((r->left==NULL) && (r->right==NULL)) return 1;
	if ((r->left==NULL) && (r->val>=r->right->val)) return 2;
	if ((r->right==NULL) && (r->val>=r->left->val)) return 2;
	if ((r->val<r->left->val) ||(r->val<r->right->val))  //Not a BST
	{
		NQ.add(r->left);
		NQ.add(r->right);
		return 0;
	}
	else return 3+BST(r->left)+BST(r->right);
}

TNode *Max(TNode *r){
	int max = 0, count = 0;
	TNode *tmp, *n;
	NQ.add(r);
	while (!NQ.empty())
	{
		n = NQ.front();
		NQ.pop();
		count = BST(n);
		if (count=>max)  //keep the first case alive
		{
			max = count;
			tmp = n;
		}
	}
	
	return tmp;
}
 

}

public class LargestBSTSubTree {
	class BinaryTree {
		int data;
		BinaryTree left;
		BinaryTree right;
	}

	public BinaryTree findLagestSubTree(BinaryTree root) {
		BinaryTree largestBST = null;
		Integer min = Integer.MAX_VALUE;
		Integer max = Integer.MIN_VALUE;
		Integer maxNodes = Integer.MIN_VALUE;
		findLargestBSTSubTreeUtil(root, min, max, maxNodes, largestBST);
		return largestBST;
	}

	private int findLargestBSTSubTreeUtil(BinaryTree root, Integer min,
			Integer max, Integer maxNodes, BinaryTree largestBST) {
		if (root == null) {
			return 0;
		}
		boolean isBST = true;
		
		int leftBSTNodes = findLargestBSTSubTreeUtil(root.left, min, max,
				maxNodes, largestBST);
		int currMin = (leftBSTNodes == 0) ? root.data : min;
		if (leftBSTNodes == -1 || (leftBSTNodes != 0 && root.data <= max)) {
			isBST = false;
		}

		int rightBSTNodes = findLargestBSTSubTreeUtil(root.right, min, max,
				maxNodes, largestBST);
		int currMax = (rightBSTNodes == 0) ? root.data : max;
		if (rightBSTNodes == -1 || (rightBSTNodes != 0 && root.data >= min)) {
			isBST = false;
		}
		
		if (isBST) {
			min = currMin;
			max = currMax;
			int totalNodes = leftBSTNodes + rightBSTNodes + 1;
			if (totalNodes > maxNodes) {
				maxNodes = totalNodes;
				largestBST = root;
			}
			return totalNodes;
		} else {
			return -1;
		}
	}

	public static void main(String[] args) {

	}

}

int largest(struct node*root){
int left,right;
if(root==NULL) return 0;
else if(root->left==NULL && root->right==NULL) return 1;
else{
left=largest(root->left);
right=largest(root->right);
if(root->left==NULL)
if(root->data<root->right->data)
return right+1+left;
else
return right;
else if(root->right==NULL)
if(root->data>root->left->data)
return left+1+right;
else
return left;
else if(root->data>root->left->data && root->data<root->right->data)
return left+right+1;
else return left>right?left:right;
}
}

int FindBST(struct Node *node,int min,int max,int &maxnodes,struct Node *& root,struct Node *& child)
{
if(node==NULL)
return 0;
if(node->data>min && node->data<max)
{
int leftnodes=FindBST(node->left,min,node->data,maxnodes,root,child);
struct Node *left=(leftnodes?child:NULL);
int rightnodes=FindBST(node->right,node->data,max,maxnodes,root,child);
struct Node *right=(rightnodes?child:NULL);

struct Node *parent=NewNode(node->data);
parent->left=left;
parent->right=right;

child=parent;

int count=leftnodes+rightnodes+1;
if(count>maxnodes)
{
maxnodes=count;
root=parent;
}
return count;
}
else
{
FindBST(node,-999,999,maxnodes,root,child);
return 0;
}
}

Can we do a inorder travelsal of the tree - return as an array and the longest sorted portion of the array would be the largest BST in the binary tree

found the drawback in the algo