Validate Binary Search Tree
Determine if a given binary tree is a valid Binary Search Tree (BST).
Examples
All trees defined in level-order root = [5, 2, 6] output: true root = [5, 2, 4, null, null, 3, 6] output: false root = [] output: true
In these examples, the output is true if the given binary tree root is a valid BST, and false otherwise.
Our solution to validate whether a binary tree is a Binary Search Tree (BST) uses a recursive approach. We traverse the tree while maintaining a range for valid node values (min and max). At each node, we check whether its value lies within the given range:
- If the node’s value is not within the allowed range, we return
False, indicating the tree is not a valid BST. - If the node’s value is valid, we recursively check its left and right subtrees:
- The left subtree must have values strictly less than the current node's value.
- The right subtree must have values strictly greater than the current node's value.
For the left subtree, the range becomes (min, current_node_value). For the right subtree, the range becomes (current_node_value, max).
We use nullptr to indicate unbounded ranges when there is no minimum or maximum restriction (e.g., for the root node or outermost nodes).
If all nodes satisfy their respective conditions, we return True, confirming that the tree is a valid BST.
from typing import Optional
class TreeNode:
def __init__(self, val: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
self.val = val
self.left = left
self.right = right
def is_valid_bst(root: Optional[TreeNode], low: Optional[int] = None, high: Optional[int] = None) -> bool:
if not root:
return True
if (low is not None and root.val <= low) or (high is not None and root.val >= high):
return False
return is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)Time Complexity: The solution has a time complexity of O(n), where n is the number of nodes in the binary tree. This is because we traverse each node exactly once, performing constant-time checks at each node.
Space Complexity: The space complexity is O(h), where h is the height of the tree. This space is used by the recursion stack. In the worst case (for an unbalanced tree), the height could be n, making the space complexity O(n). For a balanced tree, the height would be O(log n).
bool isValidBST(TreeNode* root, long min = LONG_MIN, long max = LONG_MAX){ if (root == NULL) return true; if (root->val <= min || root->val >= max) return false; return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max); }