Validate Binary Search Tree

Check whether every node follows all BST ordering rules.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Validate Binary Search Tree: Validate each node against the complete interval inherited from every ancestor.

Input and goalCheck whether every node follows all BST ordering rules.

Call valid(5, -inf, inf)The root 5 satisfies -inf < 5 < inf, so recursively validate its left subtree before its right subtree.

5check -inf < 5 < inf/\17/\48

inputtree=[5,1,7,null,null,4,8]activeCheckcheck -inf < 5 < infstackvalid(5,-inf,inf)

Recognize it

BST validity applies against every ancestor, so a local parent-child comparison is insufficient and each recursive call must carry the legal value interval.

Keep true

At valid(node, low, high), every ancestor constraint is summarized by low < node.val < high; the left call tightens high and the right call tightens low.

Reuse it

When a recursive descendant must satisfy all ancestor decisions, summarize those decisions as constraints in the call state rather than rechecking only the parent.

Pattern: DFS with valid lower and upper bounds.

Simple idea: A node in a left subtree must be below every ancestor bound, not only its parent. Pass the allowed value range down the tree.

def is_valid_bst(root: TreeNode | None) -> bool:
   def valid(node: TreeNode | None, low: float, high: float) -> bool:
      if node is None:
         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"))

Cost: $O(n)$ time and $O(h)$ call-stack space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.