# Two solutions of this question. In-order traverse and recursion by keep tracking bound.

• Solution 1:
In-order traverse

``````class Solution {
public:
bool InOrder(TreeNode* node, long& num){
if(node==NULL)
return true;

bool r0=InOrder(node->left, num);
bool r = node->val > num;
num = node->val;
bool r1=InOrder(node->right, num);

return r0&&r&&r1;
}

bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
long num=long(INT_MIN)*2;
return InOrder(root, num);
}
};
``````

Solution 2:
Recursively check whether the BST properties are kept in left and right subtrees. In the meantime, we need to keep tracking the low and high bound of each side.

`````` class Solution {
public:
bool helper(TreeNode* root, long lowBound, long highBound){
if(root==NULL)
return true;

bool left=root->left==NULL? true:(root->left->val < root->val) && (root->left->val > lowBound);
bool right=root->right==NULL? true:( root->right->val > root->val) && (root->right->val < highBound);

bool leftForest=helper(root->left, long(lowBound), min(long(highBound), long(root->val)));
bool rightForest=helper(root->right, max(long(lowBound), long(root->val)), long(highBound));

return left && right && leftForest && rightForest;
}

bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
return helper(root, long(INT_MIN)*2, long(INT_MAX)*2); // To tackle to corner case, multiply with 2.
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.