isBST() , Largest BST in a Binary Tree & Largest BST subtree

Write an isBST() function that returns true if a tree is a binary search tree and false otherwise.
Explore both the iterative and recursive versions

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

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

Method 1:Max value of subtree method
For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

Code 1.1:Iterative

int isBST(struct node* node)
{
  if (node == NULL)
    return(true); 
  
  if (node->left!=NULL && maxValue(node->left) > node->data)
    return(false); 

  if (node->right!=NULL && minValue(node->right) <= node->data)
    return(false); 

  if (!isBST(node->left) || !isBST(node->right))
    return(false); 

  return(true);
}

Code 1.2:Recursion

bool isSubTreeLessThan(struct tree *p, int val) {
  if (!p) return true;
  return (p->data < val &&
          isSubTreeLessThan(p->left, val) &&
          isSubTreeLessThan(p->right, val));
}

bool isSubTreeGreaterThan(struct tree *p, int val) {
  if (!p) return true;
  return (p->data > val &&
          isSubTreeGreaterThan(p->left, val) &&
          isSubTreeGreaterThan(p->right, val));
}

bool isBSTBruteForce(struct tree *p) {
  if (!p) return true;
  return isSubTreeLessThan(p->left, p->data) &&
         isSubTreeGreaterThan(p->right, p->data) &&
         isBSTBruteForce(p->left) &&
         isBSTBruteForce(p->right);
}

Time:The complexity of brute force solution is n*n in the worst case.
Explanation:
Suppose the BST is in the form of a linear list,i.e, all elements inserted in a sorted order(all left pointers will be NULL), then for each node, we compare its value with all of the node on the right and we get a count as
n-1 — for the first node
n-2 — for the second node
.
.
1 — for the pen-ultimate node
0 — for the last node
i.e. (n-1) + (n-2) + (n-3) + … + 2 + 1 = n*(n-1)/2 ====== O(n^2).

Method 2:Efficient Storing Method--O(n)
Method 1 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.


#include <limits.h>

int isBST(struct node* node)

{

  return(isBSTUtil(node, INT_MIN, INT_MAX));

}

int isBSTUtil(struct node* node, int min, int max)

{

  if (node==NULL)

     return 1;

  if (node->data < min || node->data > max)

     return 0; 

  return

    isBSTUtil(node->left, min, node->data) &&

    isBSTUtil(node->right, node->data+1, max);

} 

Alternatively,

bool isBSTHelper(struct node *p, int low, int high) {

  if (!p) return true;

  if (low < p->data && p->data < high)

    return isBSTHelper(p->left, low, p->data) &&

           isBSTHelper(p->right, p->data, high);

  else

    return false;

}

bool isBST(struct node *root) {

  // INT_MIN and INT_MAX are defined in C++'s <climits> library

  return isBSTHelper(root, INT_MIN, INT_MAX);

}

This algorithm runs in O(N) time, where N is the number of nodes of the binary tree. It also uses O(1) space (neglecting the stack space used by calling function recursively).


Method 3:Inorder Traversal Method---O(n)

While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is greater than the previous value then tree is not BST
The use of static variable can also be avoided by using reference to prev node as a parameter

bool  isBST(struct node* root)
{
    static struct node *prev = NULL;

    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        if (prev != NULL && root->data < prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }
    return true;
}

Alternatively,

bool isBSTInOrderHelper(struct tree *p, int& prev) {

  if (!p) return true;

  if (isBSTInOrderHelper(p->left, prev)) {

    if (p->data > prev) {

      prev = p->data;

      return isBSTInOrderHelper(p->right, prev);

    } else {

      return false;

    }

  }

  else {

    return false;

  }

}

Method 4:Non Recursive Way

http://codesam.blogspot.in/2011/03/determine-if-binary-tree-is-binary.html

Useful Links:
http://www.leetcode.com/2010/09/determine-if-binary-tree-is-binary.html