For a strict BST, every left-subtree value < node.val < every right-subtree value. Validate by inherited (low,high) bounds or strictly increasing inorder prev. Search discards an entire subtree after each comparison. Duplicate policy must be explicit.
Recognition signals
The structure is explicitly a binary search tree.
The task asks for validation, lookup, kth smallest, predecessor/successor, or range pruning.
Inorder position matches value order.
Comparing with a target eliminates a whole left or right subtree.
Ancestor bounds matter beyond direct parent-child comparisons.
False friends
Signal
Why it is different
An ordinary binary tree
Without global ordering, value-based pruning and sorted inorder are invalid.
Checking only direct children
A distant descendant can violate an ancestor bound while satisfying its local parent comparison.
Duplicates with unspecified placement
Strict, equal-left, and equal-right policies change bounds and inorder comparisons.
Core invariant
At node entry, (low,high) is the intersection of all ancestor constraints; a legal value lies inside it. In inorder form, every visited value is greater than the previous one.
State, transition, and processing order
Item
Definition
State
Current node plus ancestor bounds, or an iterative inorder stack with prev and optional visit rank.
Transition
Validation sends (low,node.val) left and (node.val,high) right; rank queries increment when an inorder node is popped.
def is_valid_bst(root):
stack, node = [], root
prev = None
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if prev is not None and node.val <= prev:
return False
prev = node.val
node = node.right
return True
Correctness sketch
The BST definition makes inorder visit all smaller left values, then the node, then all larger right values, so a valid tree is strictly increasing.
Conversely, a strictly increasing inorder segment puts every left-subtree value before and below its node and every right value after and above it, recursively satisfying global order.
The template checks every adjacent inorder pair, exactly testing this equivalent condition.
Complexity
Time
Space
Parameters
O(n) validation/full traversal; search is O(h), O(log n) only when balanced and O(n) worst-case
O(h) stack
n is node count and h tree height.
Edge cases
empty tree
duplicate policy
avoiding finite sentinels at numeric extremes
prev equal to zero with negative values
skewed depth
kth query outside node count
Error patterns
Pattern
Why it fails / fix
Comparing only immediate children
It misses a right-descendant value below a distant ancestor; use inherited bounds or global inorder.
Using a finite integer as infinity
A node may equal that sentinel; use None or mathematical infinity.
Testing prev by truthiness
Zero is a valid previous value; test prev is not None.
Assuming every BST is balanced
Search is O(h), and a skewed tree has h=n.
Selection and exclusion rules
Confirm BST semantics and duplicate policy first.
Validate with ancestor bounds or inorder prev, never only child comparisons.
Use inorder for rank or ordered output.
Use target comparisons to prune to one path for lookup.