TL;DR
Recurse carrying an allowed (low, high) interval for each node — O(n) time, O(h) space (h = tree height). The inorder-monotonic check is the classic equal-cost alternative.
Approach 1 — Brute force: validate each node against its whole subtree
The naive intuition takes the definition literally: for every node, the maximum of its left subtree must be less than it, and the minimum of its right subtree must be greater. So at each node we scan both subtrees to find their extremes.
# 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:
def subtree_max(node: Optional[TreeNode]) -> float:
if not node:
return float("-inf")
return max(node.val, subtree_max(node.left), subtree_max(node.right))
def subtree_min(node: Optional[TreeNode]) -> float:
if not node:
return float("inf")
return min(node.val, subtree_min(node.left), subtree_min(node.right))
def valid(node: Optional[TreeNode]) -> bool:
if not node:
return True
if node.left and subtree_max(node.left) >= node.val:
return False
if node.right and subtree_min(node.right) <= node.val:
return False
return valid(node.left) and valid(node.right)
return valid(root)
Complexity: O(n^2) time (each node re-scans its subtree), O(h) space. With n up to 10^4 this is roughly 10^8 operations on a skewed tree — the repeated full-subtree scans are the waste the better approaches remove.
Approach 2 — Recursive bounds (top-down interval)
The insight: instead of asking each node to inspect its descendants, pass constraints downward. Every node must lie strictly inside an open interval (low, high). The root starts with (-inf, +inf). When you descend left, the current node’s value becomes the new upper bound; when you descend right, it becomes the new lower bound. A single pass then suffices.
# 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:
def valid(node: Optional[TreeNode], low: float, high: float) -> bool:
if not node:
return True
if not (low < node.val < high):
return False
return (valid(node.left, low, node.val)
and valid(node.right, node.val, high))
return valid(root, float("-inf"), float("inf"))
Walkthrough on [5, 1, 4, null, null, 3, 6]:
valid(5, -inf, +inf): 5 is inside, recurse.- Left
valid(1, -inf, 5): 1 inside, its children are null → True.
- Right
valid(4, 5, +inf): check 5 < 4 < +inf → 4 is not greater than 5, condition fails → return False.
The whole tree short-circuits to False, and crucially we never even reach the deeper 3/6 — the bound caught the violation at 4. Using float("-inf")/float("inf") sidesteps the trap where a real node value equals 2^31 - 1.
Complexity: O(n) time (each node visited once), O(h) space for the recursion stack.
Approach 3 — Inorder traversal must be strictly increasing
The insight: an inorder traversal (left, node, right) of a valid BST yields values in strictly ascending order. So walk inorder while tracking only the previously visited value; the first time a value is not strictly greater than its predecessor, the tree is invalid. This uses an explicit stack, avoiding recursion depth limits on skewed trees.
# 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:
stack: List[TreeNode] = []
prev: float = float("-inf")
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if node.val <= prev:
return False
prev = node.val
node = node.right
return True
Walkthrough on [2, 1, 3]: inorder visits 1, then 2, then 3. Each is strictly greater than prev (-inf → 1 → 2 → 3), so we return True.
Complexity: O(n) time, O(h) space for the stack.
Common pitfalls
- Only comparing with immediate children. This wrongly accepts trees where a deep node violates a distant ancestor’s bound. The interval or inorder methods fix this.
- Using
<= where strict < is required. Equal values are invalid in a BST; an off-by-one here silently accepts duplicates.
- Sentinel bounds that node values can reach. Initializing bounds with
2^31 numeric limits collides with real values at the extremes — use float("-inf")/float("inf"), or pass the node reference (None) as the “no bound yet” marker.
- Assuming recursion always fits. A degenerate tree of
10^4 nodes forms a chain; the iterative inorder version avoids hitting Python’s recursion limit.
Pattern takeaway
When a per-node property actually depends on a node’s entire ancestry, don’t re-derive it from scratch at every node — thread the accumulated constraint down through the recursion. And whenever a BST appears, remember its signature: inorder is sorted. That single fact turns many “validate / find kth / find closest” BST questions into simple linear scans.