Take the 2-minute tour ×

I was asked this question in an interview. I started my answer with the naive approach of finding all the subtree and checking if any of them is a bst. In the process, we will record the size of max bst seen so far.

Is there a better approach than this?

share|improve this question

5 Answers 5

What if you do this:

  1. Reverse the weight of your graph
  2. Use Kruskal algorithm in this way.

a. Select the lowest wheighted edge from your set of edges.

b. Create a tree only if adding that edge doesn't break your bst constraint.

c. Remove that edge from your edges set.

You might end up with several trees (Since discarding edges when bst constraint is not satisfied could make you disconnect your original graph), so just select the one with more nodes.

share|improve this answer

I think of your solution like this:

for each subtree of the tree:
    if the subtree is a binary search tree:
        compute its size
        if it is the largest one found so far:
            best = subtree
return best

This is inefficient because it does O(n) work for each subtree, and there are up to n subtrees.

You can do better by walking the whole tree only once.

// Walk the subtree at node. Find the largest subtree that is a binary search tree
// and return that tree in *result. Also return that subtree's size and the range
// of values it covers in *size, *min, and *max.
walk(Node *node, Node **result, size_t *size, Value *min, Value *max)
    Node *result0 = NULL;
    size_t size0 = 0;
    Value min0, max0;
    if (node->left)
        walk(node->left, &result0, &size0, &min0, &max0);

    Node *result1 = NULL;
    size_t size1 = 0;
    Value min1, max1;
    if (node->right)
        walk(node->right, &result1, &size1, &min1, &max1);

    // If both subtrees are search trees and node->value falls between them,
    // then node is a search tree.
    if (result0 == node->left
        && result1 == node->right
        && (node->left == NULL || max0 <= node->value)
        && (node->right == NULL || node->value <= min1))
        *result = node;
        *size = size0 + 1 + size1;
        *min = node->left == NULL ? node->value : min0;
        *max = node->right == NULL ? node->value : max1;
    } else if (size0 >= size1) {
        *result = result0;
        *size = size0;
        *min = min0;
        *max = max0;
    } else {
        *result = result1;
        *size = size1;
        *min = min1;
        *max = max1;

Node *
findLargestBinarySearchSubtree(Node *root)
    Node *result;
    size_t size;
    Value min, max;
    walk(root, &result, &size, &min, &max);
    return result;
share|improve this answer
I gave +1, because this is the only answer that isn't O(n^2) and isn't obviously incorrect; however, notice that this algorithm only returns FULL subtrees. It is possible that the largest BST subtree would only be part of a full subtree. Taking this into the account is more difficult, but it's still possible to do in O(n). See this question. –  BlueRaja - Danny Pflughoeft Aug 30 '12 at 13:53
Yes, that's true. I interpreted "subtree" the way I normally would in programming, but the mathematical sense is likely what's intended here, and that would make my answer wrong. –  Jason Orendorff Aug 30 '12 at 13:56

This website seems to cover this problem under: Binary Search Tree Checking. Specifically, here's the excerpt to the solution in C++

 Returns true if the given tree is a binary search tree 
 (efficient version). 
int isBST2(struct node* node) { 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
 Returns true if the given tree is a BST and its 
 values are >= min and <= max. 
int isBSTUtil(struct node* node, int min, int max) { 
  if (node==NULL) return(true);

  // false if this node violates the min/max constraint 
  if (node->data<min || node->data>max) return(false);

  // otherwise check the subtrees recursively, 
  // tightening the min or max constraint 
    isBSTUtil(node->left, min, node->data) && 
    isBSTUtil(node->right, node->data+1, max) 
share|improve this answer
This solution just checks whether a given tree is a binary search tree. My question is to find the largest subtree in a binary tree which is BST. –  Chander Shivdasani Aug 30 '12 at 6:02

I assume there is O(n) complexity to solve.

bool is_bst(node * cur)
   if (cur == NULL)
     return true;

   // if calculated before cur vertex.
   if (hash_set_bst[cur] != -1)
      return hash_set_bst[cur];

   int left_value = MIN;
   int right_value = MAX;
   if (cur -> left != NULL)
      left_value = cur -> left -> value;
   if (cur -> right != NULL)
      right_value = cur -> right -> value;

   if (cur -> value > left_value && cur -> value < right_value)
      hash_set_bst[cur] = is_bst(cur->left) && is_bst(cur->right);
      return hash_set_bst[cur];
      hash_set_bst[cur] = 0;
      return hash_set_bst[cur];

Now for each node you know if it can start BST or not. Now you need to calculate sub tree sizes and then iterate throgh all nodes and figure out what's the max size having flag if node can start BST.

To calculate sizes you may do the following:

int dfs(node * cur)
   if (cur == NULL) return 0;
   size[cur] = 1 + dfs(cur->left) + dfs(cur->right);
   return size[cur];
share|improve this answer

do an in order traversal of the binary tree, if any subtree is BST, in order traversal will produce an ascending sequence, record the size of the tree as you go. when u hit a break point, recursive in order traversal that tree using the break point as root, record its size. pick the biggest one.

share|improve this answer

Your Answer


