Given the root of a binary tree, determine if it is a valid binary search tree (BST).
Definition of BST
- The left subtree of a node contains only nodes with keys strictly less than the node’s key.
- The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
- Both left and right subtrees must also be binary search trees.
Input / Output
Input: root = [2,1,3]
Output: true
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, which violates BST property.
Approach
- Use recursion with range limits.
- At each node, ensure its value is within valid range:
(lo < node.val < hi). - Update the range for the left and right child accordingly.
- Base case: null nodes are valid BSTs.
Time & Space Complexity
- Time Complexity: O(n) — visit each node once.
- Space Complexity: O(h) — where h is the height of the tree due to recursion stack.
var isValidBST = function (curr, lo = null, hi = null) {
if (!curr) return true;
if ((lo !== null && curr.val <= lo) ||
(hi !== null && curr.val >= hi)) {
return false;
}
let isLeftBST = isValidBST(curr.left, lo, curr.val);
let isRightBST = isValidBST(curr.right, curr.val, hi);
return isLeftBST && isRightBST;
};
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isValidBST(TreeNode* root, TreeNode* lo = nullptr, TreeNode* hi = nullptr) {
if (!root) return true;
if ((lo && root->val <= lo->val) || (hi && root->val >= hi->val)) return false;
return isValidBST(root->left, lo, root) && isValidBST(root->right, root, hi);
}
// Definition for a binary tree node
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isValidBSTHelper(struct TreeNode* root, long long lo, long long hi) {
if (!root) return true;
if (root->val <= lo || root->val >= hi) return false;
return isValidBSTHelper(root->left, lo, root->val) &&
isValidBSTHelper(root->right, root->val, hi);
}
bool isValidBST(struct TreeNode* root) {
return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, null, null);
}
private boolean validate(TreeNode node, Integer lo, Integer hi) {
if (node == null) return true;
if ((lo != null && node.val <= lo) || (hi != null && node.val >= hi)) return false;
return validate(node.left, lo, node.val) &&
validate(node.right, node.val, hi);
}
}
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isValidBST(root, lo=None, hi=None):
if not root:
return True
if (lo is not None and root.val <= lo) or (hi is not None and root.val >= hi):
return False
return isValidBST(root.left, lo, root.val) and isValidBST(root.right, root.val, hi)
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool IsValidBST(TreeNode root) {
return Validate(root, null, null);
}
private bool Validate(TreeNode node, int? lo, int? hi) {
if (node == null) return true;
if ((lo != null && node.val <= lo) || (hi != null && node.val >= hi)) return false;
return Validate(node.left, lo, node.val) && Validate(node.right, node.val, hi);
}
}
