CareerCup

/* Check for binary tree whether its binary search tree */
	private static boolean isBST(BSTNode root, int prev) {
		if(root==null)
			return true;
		if(!isBST(root.getLeft(),prev))
			return false;
		if(root.getData()<prev)
			return false;
		prev=root.getData();
		
		return isBST(root.getRight(),prev);
	}

/* check for BST */
	private static boolean isBST(BSTNode root) {
		if (root == null)
			return true;

		if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
			return false;
		if (root.getRight() != null
				&& findMin(root.getRight()) < root.getData())
			return false;

		if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
			return false;
		return true;
	}

We have to traverse the tree and check the validity at each node. Even though this condition is often expressed as:

max(left_child) < node_value < min(right_child)

which lead to the following code

bool isBST(Node* node) {
	if (node == nullptr)
		return true;
       bool condition = (maxBT(node->left) < node->value) && (node->value < minBT(node->right));
	return condition && isBST(node->left) && isBST(node->right);
}

int maxBT(Node* node){
	if (node == null_ptr)
		return INT_MIN;
	return std::max(maxBT(node->left), std::max(node->value, maxBT(node->right))); 
}

int minBT(Node* node){
	if (node == null_ptr)
		return INT_MAX;
	return std::min(minBT(node->left), std::min(node->value, minBT(node->right))); 
}

The complexity of this approach is O(N^2) as the minBT and maxBT is computed on fly.
There are several ways to improve the complexity to O(N)

(1) Compute min value and max value at each node on separated passes and cache the result using hash_map. The comparison is then performed on lookup value in constant time

unordered_map<Node*, int> max_map;
unordered_map<Node*, int> min_map;

int maxBT(Node* node){
	if (node == null_ptr) {
		max_map[node] = INT_MIN;
		return INT_MIN;
	}
	int max_value = std::max(maxBT(node->left), std::max(node->value, maxBT(node->right))); 
	max_map[node] = max_value;
	return max_value;
}
// Similar function for minBT to compute min_map

bool isBST(Node* node) {
	if (node == nullptr)
		return true;
       bool condition = (max_map[node->left] < node->value) && (node->value < min_map[node->right]);
	return condition && isBST(node->left) && isBST(node->right);
}

(2) We combine validation, minimum and maximum processes into one post-order traversal that compute the minimum, maximum and validation at the same time.

tuple<int, int, bool> MaxMinValid_helper(Node* node) {
	if (node == nullptr)
		return make_tuple(INT_MIN, INT_MAX, true);
	auto left_res = MaxMinValid_helper(node->left); 
	auto right_res = MaxMinValid_helper(node->left); 

	auto max_value = std::max(left_res.get<0>(), right_res.get<0>());
	auto min_value = std::min(left_res.get<1>(), right_res.get<1>());
	bool valid = (left_res.get<0>() < node->value) && (node->value < right_res.get<1>()) && left_res.get<2>() && right_res.get<2>();
 	return make_tuple(max_value, min_value, valid);
}

bool isBST(Node* root) {
	return MaxMinValid_helper(root).get<2>();
}

(3) The simplest method, however, is based on observation that as long as the value of the current node is in the range determined by its parent then the BST is valid. In particular

* The valid range for left child is [parent->range_min, parent->value];
* The valid range for right child is [parent->value, parent->range_max];

For the root node the range is [INT_MIN, INT_MAX] which lead to the following code

bool isBST_helper(Node* node, int range_min, int range_max) {
	if (node == nullptr) return true;
	return (range_min < node->value) && (node->value < range_max) 
	&& isBST_helper(node->left, range_min, node->value)
	&& isBST_helper(node->right, node->value, range_max);
}

bool isBST(Node* root) {
	return isBST_helper(root, INT_MIN, INT_MAX);
}

(4) Other solution as Furquan mentioned is to based on the unique properties of BST is that in order traversal of BST return the sorted array so of course you can traverse the tree to build the in-order array of the values and then check if it is sorted. In practice however we don't need to store the in-order result as we can combine the check into our in-order traversal to compare the current value at the node to the immediately prior node in the traversal order (pvalue). I initialize the pvalue with INT_MIN to remove the check of validity of pvalue

bool isBST_helper(Node* node, int& pvalue) {
    if (node == nullptr) return true;
    if (isBST_helper(node->left, pvalue))
       if (node->value <= pvalue) {
            pvalue = node->value();
            return isBST_helper(node->right, pvalue);
       }
    return false;
}
bool isBST(Node* root) {
    int pvalue = INT_MIN;
    return isBST_helper(root, pvalue);
}

There is one more solution to this problem, which provides the result in O(n):

bool inorder_check(NODE *node, NODE **prev)
 {
  // Exit condition for recursion
  if (node == NULL)
   return TRUE;
   
  // First go to left child
  if(inorder_check(node->left, prev) == FALSE)
   return FALSE;
  
  // Check the current node
  if (*prev != NULL) {
   If ((*prev)->data > node->data)
    return FALSE;
  }
  // Update the previous node
  *prev = node;
  
  // Now go to right child
  return inorder_check(node->right, prev);
 }
 
 bool check_BST(NODE *root)
 {
  NODE *prev = NULL;
  return inorder_check(root,&prev);
 }

Detailed explanation can be found here:
preparefortechinterview.blogspot.com/2013/09/am-i-bst.html

This method may be helpful though signature of the method is little different.

int customInorderTraversal(TreeNode *rootnode){
	int maxval;

	if(rootnode != NULL){
		maxval = rootnode->val;
		int maxleft = maxval;
		int maxright = maxval;
		if(rootnode->left != NULL)
			maxleft = customInorderTraversal(rootnode->left);
		if(rootnode->right != NULL)
			maxright = customInorderTraversal(rootnode->right);

		if(maxleft == INT_MIN || maxright == INT_MIN){
			return INT_MIN;
		}else{
			if(maxleft <= maxval && maxval <= maxright){
				return maxright;
			}else{
				return INT_MIN;	
			}
    	}
	}else{
		return INT_MAX;
	}
}

int main(){
	TreeNode* rootnode = (TreeNode*) new TreeNode(4);
    createTree(rootnode);
	int ret = customInorderTraversal(rootnode);
	if(ret == INT_MIN){
		cout<<"\n Input Btree is not BST ";
	}else if(ret == INT_MAX){
		cout<<"\n Empty Tree";
	}else{
		cout<<"\n Input BTree is BST";
	}
}

method (3) suggested by LinhHA05 seems the best one to remember. I had used in the past

bool isBSTUtil(struct node *root, int min, int max)
{
  if(root==NULL) 
        return true;
  if((root->data <= min) || (root->data > max)) 
        return false;
  if(!isBSTUtil(root->left, min, root->data) || !isBSTUtil(root->right, root->data,max)) 
        return false;
  return true;
}

bool isBST(struct node *root) {
  if(isBSTUtil(root, INT_MIN,INT_MAX ))
        return true;
  return false;
}

See also oj.leetcode.com/problems/validate-binary-search-tree/

My solution:

private int max = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
    	if (root == null) return true;
        boolean isLeftValid = isValidBST(root.left);
        if (!isLeftValid) return false;
        if (root.val <= max) return false;
        max = root.val;
        return isValidBST(root.right);
    }

Keep an out-side array and fill it by in-order traversal - if this array is ascending then we have a BST

function func($root) {
	$arr = array(-10000);
	inOrderCheck($root,$arr);
	return $arr !== false;
}

function inOrderCheck($node,&$arr) {
	if ($node) {
		inOrderCheck($node['left'],$arr);
		if ($arr !== false && end($arr) < $node['val']) {
			$arr []= $node['val'];
		} else {
			$arr = false;
		}	
		inOrderCheck($node['right'],$arr);
	}
}

Can't it be this simple? I was amazed at the complex code above. If I am not right, please correct me. Thanks in advance!

Write it in Java, as the language choice is not important.

boolean isBST(Node node) {
    if (node == null) return true;
    
    return node.getLeft.value < n && node.getRight.value > n && 
        isBST(node->getLeft()) && isBST(node->getRight());
}