CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
Chander Shivdasani
Chander Shivdasani

Reputation: 10121

Given a Binary Tree, find the largest subtree which is a Binary Search Tree

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?

Upvotes: 1

Views: 3198

Answers (5)

danielrvt
danielrvt

Reputation: 10906

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.

Upvotes: 4

Jason Orendorff
Jason Orendorff

Reputation: 45086

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

Upvotes: 2

yngccc
yngccc

Reputation: 5684

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.

Upvotes: 1

Roman Dzhabarov
Roman Dzhabarov

Reputation: 521

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];
   }
   else
   {
      hash_set_bst[cur] = 0;
      is_bst(cur->left);
      is_bst(cur->right);
      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];
}

Upvotes: 1

badunk
badunk

Reputation: 4350

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 
  return 
    isBSTUtil(node->left, min, node->data) && 
    isBSTUtil(node->right, node->data+1, max) 
  ); 
}

Upvotes: 1

Related Questions