Finding the largest subtree in a BST

Question

Given a binary tree, I want to find out the largest subtree which is a BST in it.

Naive approach:

I have a naive approach in mind where I visit every node of the tree and pass this node to a isBST function. I will also keep track of the number of nodes in a sub-tree if it is a BST.

Is there a better approach than this ?

Answer 1

I have posted the full solution and explanation in my blog:

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

The idea is to do a depth-first traversal and pass min and max values bottom-up instead of top-down. In other words, we verify the deeper nodes before we verify if the above nodes satisfy the BST requirements.

The main reason of doing this is when one of the nodes does not satisfy the BST properties, all subtrees above (which includes this node as well) must also not satisfy the BST requirements.

As compared to the top-down approach, the bottom-up approach is such an awesome choice because the results for total number of nodes could be passed up the tree. This 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.

This algorithm runs in O(N) time complexity and O(1) space, which is as efficient as it can be. (where N is the total number of nodes in the binary tree).

Below is the C++ code that works. The tricky part of the implementation is taking care of how min and max values are passed bottom-up. Please note that I did not initialize min and max values as they are initialized in the bottom of the tree.

// Find the largest BST subtree in a binary tree.
// If the subtree is a BST, return total number of nodes.
// If the subtree is not a BST, -1 is returned.
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
                   int &maxNodes, BinaryTree *& largestBST) {
  if (!p) return 0;
  bool isBST = true;
  int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
  int currMin = (leftNodes == 0) ? p->data : min;
  if (leftNodes == -1 ||
     (leftNodes != 0 && p->data <= max))
    isBST = false;
  int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
  int currMax = (rightNodes == 0) ? p->data : max;
  if (rightNodes == -1 ||
     (rightNodes != 0 && p->data >= min))
    isBST = false;
  if (isBST) {
    min = currMin;
    max = currMax;
    int totalNodes = leftNodes + rightNodes + 1;
    if (totalNodes > maxNodes) {
      maxNodes = totalNodes;
      largestBST = p;
    }
    return totalNodes;
  } else {
    return -1;   // This subtree is not a BST
  }
}

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
  BinaryTree *largestBST = NULL;
  int min, max;
  int maxNodes = INT_MIN;   // INT_MIN is defined in <climits>
  findLargestBSTSubtree(root, min, max, maxNodes, largestBST);
  return largestBST;
}