Binary Tree Operations(IV) - Determine if a Binary Tree is a Binary Search Tree

This is the fourth article on binary tree operations. For other topics on binary tree, please refer to:

1. Binary Tree Operations(I)
2. Binary Tree Operations(II)
3. Binary Tree Operations(III) - Convert a Binary Tree to Down-Right Representation
4. Binary Tree Operations(IV) - Determine if a Binary Tree is a Binary Search Tree

The problem is: given a binary tree, how to determine if it is a Binary Search Tree(BST) or not? A binary search tree is a binary tree data structure which has the following properties.

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

The strategy is to recursively check (1) if the maximum value in the left subtree is smaller than the root node, and (2) if the minimum value in the right subtree is greater than the root node.

In order to implement the recursion, a helper function IsBSTHelper(TreeNode* root, int min, int max) is needed, where min and max define the range of possible values of subtree nodes. When checking a binary tree, the initial value of min is INT_MIN and the initial value of max is INT_MAX. However, when exploring the left subtree, the max will be changed to the value of root, and the min value remains; when exploring the right subtree, the min value is the value of root and the max value remains.

For complete code of checking BST, please refer to functions IsBST() and IsBSTHelper(TreeNode* root, int min, int max) in my binary tree library. Please note that, we assume a NULL node is a valid binary search tree.

bool IsBST(TreeNode* root) {
	return IsBSTHelper(root, INT_MIN, INT_MAX);
}

// Helper function for checking binary search tree
bool IsBSTHelper(TreeNode* root, int min, int max) {
	if(root==NULL)
		return true;

	assert(root->val > min && root->val < max);

	bool bst_left=true;
	bool bst_right=true;
	if(root->left!=NULL && (root->left->val >= root->val || root->left->val <= min))
		return false;
	else
		bst_left=IsBSTHelper(root->left, min, root->val);
	
	if(root->right!=NULL && (root->right->val <= root->val || root->right->val >= max))
		return false;
	else
		bst_right=IsBSTHelper(root->right, root->val, max);

	return (bst_left && bst_right);
}