98. Validate Binary Search Tree
Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 28.9%
Problem Breakdown
We are given the root of a binary tree and need to validate if it adheres to Binary Search Tree (BST) properties. A valid BST requires:
- Left Subtree: All nodes must be strictly less than the current node’s value (
node.val). - Right Subtree: All nodes must be strictly greater than the current node’s value (
node.val). - Recursive Property: Both left and right subtrees themselves must also be valid BSTs.
Key Constraints & Tricky Cases:
- Strict Inequality: Duplicates are not allowed (e.g.,
5cannot have a child with value5). If the problem allows duplicates, it would specify “less than or equal” for one side and strictly greater for the other; here we assume strict inequality based on standard BST definitions. - Global vs Local Constraints: A naive check comparing only immediate children (
left.val < parent) is insufficient because a node deep in the right subtree must still be greater than all ancestors, not just its direct parent. For example, if root is5, and we go left to-10then right to4, that4violates the BST property relative to root5. - Input Range: Node values fit within standard 32-bit integers (Python handles this natively). Tree size up to nodes.
Intuition
The first instinct is often a simple DFS traversal checking if left.val < current and right.val > current. However, as noted in the breakdown, this fails because it doesn’t track constraints propagated from ancestors.
Why Brute Force Fails:
Checking only immediate children allows invalid values deep within subtrees (e.g., value -100 is valid relative to a parent of -5, but invalid if an ancestor was 0).
Key Insight:
Every node in the tree has an implicit range (min_val, max_val) it must satisfy based on its path from the root.
- When traversing left, we tighten the upper bound: new
maxbecomes currentnode.val. - When traversing right, we tighten the lower bound: new
minbecomes currentnode.val.
We can pass these bounds down recursively (or iteratively) to validate every node against its valid range.
Approach
- Define a helper function that takes
(root, min_val, max_val)as arguments. - Base Case: If the current node is
None, returnTrue(empty subtree satisfies BST property). - Validation Check: Verify if
node.vallies strictly within(min_val, max_val). If not (<= min_valor>= max_val), returnFalse. - Recursive Step:
- Recurse on the left child with bounds:
(min_val, node.val)(upper bound tightens). - Recurse on the right child with bounds:
(node.val, max_val)(lower bound tightens).
- Recurse on the left child with bounds:
- Return
Trueonly if both recursive calls returnTrue.
Complexity Analysis
- Time: where is the number of nodes. We visit every node exactly once in a single DFS traversal.
- Space: for recursion stack space, where is the height of the tree. In a balanced tree, this is . In a skewed (linked-list-like) tree, it degrades to .
Solution
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# Helper function to traverse with bounds (min_val, max_val) exclusive.
# Using float('-inf') and 'inf' handles the initial full range safely
# without needing a sentinel node value check for min/max logic initially.
def validate(node, low, high):
if not node:
return True
# If current node violates bounds relative to ancestors, fail immediately
if not (low < node.val < high):
return False
# Recurse left with upper bound tightened by current node value
# Recurse right with lower bound tightened by current node value
return validate(node.left, low, node.val) and \
validate(node.right, node.val, high)
if not root:
return True
return validate(root, float('-inf'), float('inf'))
Edge Cases Handled
- Empty Tree: The initial check
if not roothandles a null input gracefully (though constraints specify , robustness is good). - Single Node: Returns True as the range
(min, max)allows any value for the single node. - Duplicate Values: Strict inequality (
<) ensures duplicates are rejected immediately upon encountering them in a subtree where they violate an ancestor’s constraint or direct parent comparison. - Negative Numbers: Python integers handle negative values correctly;
float('-inf')works as expected with negatives (e.g.,-10 < -5). - Skewed Trees: While recursion depth could hit limits in production environments ( skewed), this solution uses the standard recursive pattern accepted for LeetCode. In a real-world scenario, an iterative stack-based approach would be used to avoid
RecursionError.