Validate a Binary Search Tree (BST) -- LeetCode 98

[Question]:
Validate a BST: i.e. make sure all values in left sub-tree is smaller than each node's value, all values in right  sub-tree is larger than each node's value.

[Analysis]:
Using in-order traversal. Need to make sure ALL values in left/right sub-tree have to be smaller/larger than the current node, so we need to know the min and max values in the left/right sub-trees. Time complexity is O(N).

Another method is to record the previous node of visiting node A. Going through the tree in in-order, always record the previous node in visited nodes.

[Solution]:
//
// -- Using min, max of left, right subtree --
//
 bool ValidateBST(TreeNode *root, int& subMax, int& subMin) {
        int min, max;
        subMin = subMax = root->val;
        if (root->left) {
            if (!(ValidateBST(root->left, max, min) && max < root->val))
                return false;
            subMin = min;
        }
        if (root->right) {
            if (!(ValidateBST(root->right, max, min) && min > root->val))
                return false;
            subMax = max;
        }
        return true;
}

//
// -- Using previous node --
//
class Solution {
    bool validBST(TreeNode* root, TreeNode*& prev) {
        if (!root) return true;
        if (!validBST(root->left, prev)) return false;
        if (prev!=NULL && prev->val>=root->val) return false;
        prev = root;
        return validBST(root->right, prev);
    }
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* p = NULL;
        return validBST(root, p);
    }
};