Find largest BST in a binary tree

Given a Binary tree, Find largest Binary Search tree in it.

A tree is a BST if:

1. Both left and right subtrees of a node are BSTs.
2. The node’s value is greater than its left subtree’s maximum value.
3. The node’s value is less than its right subtree’s minimum value.

Top-Down approach : Starting from the root, we process in the order of current node, left child, then right child. For each node, call isBST() to check if the current subtree is a BST. If it is, then we have found the largest BST subtree. If it is not, then check its left and right child. If only one of the subtrees is BST, then we can return that subtree. However, if both left and right subtrees are BSTs, then we have to compare which subtree is larger (has more descendant nodes), then return the larger one.

Bottom-Up Approach:In Bottom up approach, we need to pass some information up the tree. Obviously, we need to pass minimum and maximum values of the subtree as we traverse up the tree, so the above subtrees could be verified for BST’s properties.

Bottom-Up approach,as compared to the top-down approach, saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.

The run-time complexity for the bottom-up approach is O(n).Even though a node’s left subtree is not a BST, you must still continue traverse its right subtree as the largest BST subtree might be contained in its right subtree.

struct node
{
	int data;
	struct node* left;
	struct node* right;
};
int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot);

struct node* findLargestBSTSubtree(struct node *root) {
  struct node *bstRoot = NULL;
  int min, max;
  int maxNodes = INT_MIN;
  largestBST(root, min, max, maxNodes,bstRoot);
  return bstRoot;
}

int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot)
{
  if(root == NULL)
	return 0;

  int leftMin = INT_MIN, rightMin = INT_MIN;
  int leftMax = INT_MAX, rightMax = INT_MAX;
  int x,y;

  x = largestBST(root->left, leftMin, leftMax, size,bstRoot);
  y = largestBST(root->right, rightMin, rightMax, size,bstRoot);

  if(x==-1 || y ==-1)
    return -1;
  if(x==0) 
  {
	leftMax = root->data;
	leftMin = root->data;
  }
  if(y==0)
  { 
	rightMin = root->data;
	rightMax = root->data;
  }

  if(root->data < leftMax || root->data > rightMin)
    return -1;

  min = leftMin;
  max = rightMax;


  if(x+y+1 > size){
    size = x+y+1;
    bstRoot = root;
  }
  return x+y+1;
}

One Thought on “Find largest BST in a binary tree

  1. Anonymous on January 18, 2015 at 2:42 am said:

    Wrong output for this tree –
    Expected :- 5 10 15 20
    Actual :- 0 2 8
    struct node *root = newNode(15);
    root->left = newNode(10);
    root->right = newNode(20);
    root->left->left = newNode(5);
    root->left->right = newNode(7);
    root->left->right->left = newNode(2);
    root->left->right->left->left = newNode(0);
    root->left->right->left->right = newNode(8);
    root->left->right->right = newNode(5);
    root->left->right->right->left = newNode(3);

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation