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;
}

3 Thoughts 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);

  2. skartik on December 16, 2016 at 9:38 pm said:

    A better solution:

    Start from root. keep checking left and right if till current stage this tree is a BST. Keep a count of number of nodes so far. Also a count of min and max in left and right.
    Moment the tree violates being a BST. That would be due to current node being checked. the node from this violation happend, set the current node to this and then start the counting process again.

  3. skartik on December 17, 2016 at 5:27 pm said:

    int max_height_BST_in_BT(node *root, int mn, int mx) {
    if (!root)
    return 0;
    else if (root->val val > mx)
    return 1;
    else {
    return 1 + max(max_height_BST_in_BT(root->left,mn,root->val-1), max_height_BST_in_BT(root->right,root->val+1,mx));
    }
    }

    int max_height_binary_search_tree(node *start_root, node *& max_root, int mx_ht) {
    if (!start_root)
    return mx_ht;
    else {
    int mh = max_height_BST_in_BT(start_root,INT_MIN,INT_MAX);
    if (mh > mx_ht) {
    max_root = start_root;
    mx_ht = mh;
    }
    int ml = max_height_binary_search_tree(start_root->left,max_root,mx_ht);
    int mr = max_height_binary_search_tree(start_root->right,max_root,mx_ht);
    return max(max(mx_ht,ml),mr);
    }
    }

Leave a Reply to skartik Cancel 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