IsBST : Check whether the tree provided is BST or not

Problem
This background is used by the next two problems: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. To be a binary search tree, for every node, all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node. Consider the following four examples...

a.  5   -> TRUE

   / \

  2   7

b.  5   -> FALSE, because the 6 is not ok to the left of the 5

   / \

  6   7

c.   5  -> TRUE

    / \

   2   7

  /

1

d.   5  -> FALSE, the 6 is ok with the 2, but the 6 is not ok with the 5

    / \

   2   7

  / \

1     6

Solutions

There are couple of solution to this.

For the first two cases, the right answer can be seen just by comparing each node to the two nodes immediately below it. However, the fourth case shows how checking the BST quality may depend on nodes which are several layers apart -- the 5 and the 6 in that case.
Method 1 - Simple Recursive Solution BUT WRONG

int isBST(struct node* node)
{
  if (node == NULL)
    return 1;
     
  // false if left is > than node 
  if (node->left != NULL && node->left->data > node->data)
    return 0;
     
  // false if right is < than node 
  if (node->right != NULL && node->right->data < node->data)
    return 0;
   
  // false if, recursively, the left or right is not a BST 
  if (!isBST(node->left) || !isBST(node->right))
    return 0;
     
  // passing all that, it's a BST 
  return 1;
}

Here is the test case which shows it fails:

So, what's the correct solution then.

Method 2 - Correct Solution
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.

/* Returns true if a binary tree is a binary search tree */
int isBST(struct node* node)
{
  if (node == NULL)
    return(true);
     
  /* false if the max of the left is > than us */
  if (node->left!=NULL && maxValue(node->left) > node->data)
    return(false);
     
  /* false if the min of the right is <= than us */
  if (node->right!=NULL && minValue(node->right) < node->data)
    return(false);
   
  /* false if, recursively, the left or right is not a BST */
  if (!isBST(node->left) || !isBST(node->right))
    return(false);
     
  /* passing all that, it's a BST */
  return(true);
} 

It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree.
Min value from BST (more here):

int minValue(struct node* node) {
  struct node current = node;   // loop down to find the leftmost leaf
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}

Max value from BST:

int maxValue(struct node* node) {
  struct node current = node;   // loop down to find the leftmost leaf
  while (current->right != NULL) {
    current = current->right;
  }
  return(current->data);
}

Time complexity : O(n^2)
(As minValue and maxValue are O(n) )
Space Complexity : O(n) [for stack space, otherwise O(1)]

Method 3 - Efficient solution
 Method 2 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.

// 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 >max || node->data < min) return(false); 
// otherwise check the subtrees recursively, 
// tightening the min or max constraint
  return   
    isBSTUtil(node->left, min, node->data -1 ) //node->data - 1 for distinct values
    && 
    isBSTUtil(node->right, node->data+1, max)  );// for distinct values
}

Time complexity : O (n)
Space Compexity : O(n) for stack space (Otherwise O(1) as we have not used any array etc)

Method 4 - Inorder traversal (with and without aux array)
You can read about inorder traversal here.
Using aux array-
Here are the steps we have to follow:

1. Do In-Order Traversal of the given tree and store the result in a temp array.
2. Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

Time Complexity: O(n)
Space Complexity - O(n)

Without using aux array
We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST. Here is the code:

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;
 
        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;
 
        prev = root;
 
        return isBST(root->right);
    }
 
    return true;
}

The use of static variable can also be avoided by using reference to prev node as a parameter. Also, we are using calling isBST with right node after setting prev to root as we care about the next node of that root.

Method 5 - Iterative solution using BFS

The below code is just a modified version of the standard non-recursive Breadth First Search (BFS) of a binary tree. If you are unfamiliar with the algorithm for BFS, you can find detailed explanation here.

struct Node
{
  Node* left;
  Node* right;
  int value;
};

bool isBST(Node* root)
{
  if (root == NULL)
    return true;
    
  stack nodeStack;

  nodeStack.push(root);

  while (!nodeStack.empty())
  {
    Node* current = nodeStack.top();
    
    nodeStack.pop();
    
    if (current->left != NULL)
    {
      nodeStack.push(current->left);
      if (current->left->value > current->value)
        return false;
    }

    if (current->right != NULL)
    {
      nodeStack.push(current->right);
      if (current->right->value < current->value)
        return false;
    }
  }

  return true;
}

Anyway, for every node we check whether its children obey the rules of binary search tree. If the current node has a left child, the child's value must be less than the current node's value. On the other hand, if the current node has a right child, the right child's value must be greater than the current node's value. Therefore, a binary tree with all nodes that satisfy those rules is a binary tree. We return true when we check all nodes and none of them violates the rules. However, if there is any violation, we simply return false.

References

• http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/