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
Take 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. At each node, 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
def isValidBST(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 redundant work the next approaches eliminate.
Approach 2 — Recursive bounds (top-down interval)
Instead of asking each node to inspect its descendants, pass the constraints downward. Every node must lie strictly inside an open interval (low, high). The root starts with (-inf, +inf). Descending left, the current node’s value becomes the new upper bound; descending right, it becomes the new lower bound. A single pass 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
def isValidBST(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]:
flowchart TD
A["5<br/>(-inf, +inf)"] --> B["1<br/>(-inf, 5)"]
A --> C["4<br/>(5, +inf) invalid: 4 < 5"]
C --> D["3"]
C --> E["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 the deeper 3 and 6 are never visited because the bound caught the violation at 4. Using float("-inf")/float("inf") avoids the case 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
An inorder traversal (left, node, right) of a valid BST yields values in strictly ascending order. 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. The explicit stack avoids 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
def isValidBST(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 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 fact turns many “validate / find kth / find closest” BST questions into linear scans.