struct Node {
Node *left, *right;
int val;
};
// returns true if subtree at root is BST
// the pair is minval and maxval of this subtree
typedef pair pii;
pair isBST(Node *root)
{
if (root == NULL) return make_pair(true, pii(0,0));
if (root->left == NULL && root->right == NULL)
return make_pair(true, pii(root->val, root->val));
pair p1, p2;
bool b1, b2, ans;
int s1, s2, t1, t2, vmin, vmax;
p1 = isBST(root->left);
p2 = isBST(root->right);
b1 = p1.first;
s1 = p1.second.first; s2 = p1.second.second;
b2 = p2.first;
t1 = p2.second.first; t2 = p2.second.second;
if (root->left == NULL) { // only right subtree nonempty
ans = b2 && root->val <= t1;
vmin = root->val; vmax = t2;
} else if (root->right == NULL) { // only left subtree empty
ans = b1 && s2 <= root->val;
vmin = s1; vmax = root->val;
} else { // both subtree nonempty
ans = b1 && b2 && s2 <= root->val && root->val <= t1;
vmin = s1; vmax = t2;
}
return make_pair(ans, pii(vmin, vmax));
}
