Given the root
of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1:


Input: root = [2,1,3] Output: true
Example 2:


Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. -231 <= Node.val <= 231 - 1
Validate Binary Search Tree Solutions
✅Time: $O(n)$
✅Space: $O(n)$
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)
Watch Tutorial
Checkout more Solutions here