/**
 * For a binary search tree, the in-order traversal result is a sorted array
 */

bool isValidBST(TreeNode *n, TreeNode* &pre)
{
    if (n == NULL) return true;

    if (!isValidBST(n->left, pre))return false;
    
    if (pre != NULL &&  pre->val >= n->val) return false;

    pre = n;
    if (!isValidBST(n->right, pre))return false;

    return true;
}

bool isValidBST(TreeNode *root) 
{
    TreeNode *pre = NULL;
    return isValidBST(root, pre);
}