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

- Binary Tree Operations(I)
- Binary Tree Operations(II)
- Binary Tree Operations(III) - Convert a Binary Tree to Down-Right Representation
- 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);
}
```