• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, nullptr, nullptr);
}

private:
bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if (!root)
return true;
if (minNode && root->val <= minNode->val)
return false;
if (maxNode && root->val >= maxNode->val)
return false;

return isValidBST(root->left, minNode, root) &&
isValidBST(root->right, root, maxNode);
}
};
``````

## JAVA

``````class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}

private boolean isValidBST(TreeNode root, TreeNode minNode, TreeNode maxNode) {
if (root == null)
return true;
if (minNode != null && root.val <= minNode.val)
return false;
if (maxNode != null && root.val >= maxNode.val)
return false;

return isValidBST(root.left, minNode, root) &&
isValidBST(root.right, root, maxNode);
}
}
``````

## Python

``````class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValidBST(root: Optional[TreeNode],
minNode: Optional[TreeNode], maxNode: Optional[TreeNode]) -> bool:
if not root:
return True
if minNode and root.val <= minNode.val:
return False
if maxNode and root.val >= maxNode.val:
return False

return isValidBST(root.left, minNode, root) and \
isValidBST(root.right, root, maxNode)

return isValidBST(root, None, None)
``````

• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> stack;
TreeNode* pred = nullptr;

while (root || !stack.empty()) {
while (root) {
stack.push(root);
root = root->left;
}
root = stack.top(), stack.pop();
if (pred && pred->val >= root->val)
return false;
pred = root;
root = root->right;
}

return true;
}
};
``````

## JAVA

``````class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode pred = null;

while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pred != null && pred.val >= root.val)
return false;
pred = root;
root = root.right;
}

return true;
}
}
``````

## Python

``````class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
stack = []
pred = None

while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if pred and pred.val >= root.val:
return False
pred = root
root = root.right

return True
``````