# Three solutions in C++

• Solution 1.

BF, O(n^2).

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
if(!root) return true;
if(!isValid(root->left, root->val, true) || !isValid(root->right, root->val, false)) return false;
return isValidBST(root->left) && isValidBST(root->right);
}

bool isValid(TreeNode* root, int bound, bool isLeft){
return !root || (isLeft ? root->val < bound : root->val > bound ) && isValid(root->left, bound, isLeft) && isValid(root->right, bound, isLeft);
}
};
``````

Solution 2.

In-order, recursive, O(n), refered from here.

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode* pre = NULL;
return isValid(root, pre);
}

bool isValid(TreeNode* root, TreeNode* &pre){
if(!root) return true;
if(!isValid(root->left, pre)) return false;
if(pre && root->val <= pre->val) return false;
pre = root;
return isValid(root->right, pre);
}
};
``````

Solution 3.

In-order, iterative, O(n), refered from here.

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*>s;
TreeNode* pre = NULL;
while(root || !s.empty()){
while(root){
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if(pre && root->val <= pre->val) return false;
pre = root;
root = root->right;
}
return true;
}
};
``````

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