Given the root of a binary tree, determine whether it is a valid binary search tree: every node's value must be strictly greater than every value in its left subtree and strictly less than every value in its right subtree.
Example
Input root = [5,1,4,null,null,3,6]
Output false
Key Pointers
Checking a node only against its immediate children isn't enough — validity depends on bounds inherited from every ancestor, not just the parent.
Carry a (low, high) valid range down through the recursion; each node must fall strictly inside it, and its children inherit a narrower range.
An in-order traversal that should come out strictly increasing is an equally valid, sometimes simpler, alternative approach.
Recurse left with (low, node.val) and right with (node.val, high); return True only if both succeed.
Call valid(root, -infinity, infinity) to start.
Complexity
Time: O(n) — Space: O(h)
Code
def isValidBST(root: TreeNode | None) -> bool:
def valid(node: TreeNode | None, 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"))
Code Explanation
How the solution above works, piece by piece.
valid(node, low, high): every value in this subtree must be strictly between low and high.
An empty subtree is valid.
If the node's value is outside its range, the tree is not a BST.
Left child: same lower bound, upper bound becomes this node's value. Right child: lower bound becomes this node's value.
Start with (−∞, +∞). O(n) time, O(height) stack.
Visual Walkthrough
Running it on root = [5, 1, 4, null, null, 3, 6]:
Going left caps the range with the parent's value; going right raises its lower bound. 4 is a child of 5 on the right, so it must be greater than 5. Checking only parent–child pairs would miss violations deeper down; carrying the range catches them.