Validate Binary Search Tree
Determine if a binary tree is a valid BST: every node's left subtree values < node < right subtree values for all descendants, not just children.
Answers use simple, clear English.
Quick interview answer
DFS with an allowed (low, high) range per node. Alternatively inorder traversal must be strictly increasing.
Detailed answer
DFS with an allowed (low, high) range per node. Alternatively inorder traversal must be strictly increasing. Checking only immediate children is a common bug — duplicates and equal bounds need a policy (usually strict <).
Full explanation
Checking only immediate children is a common bug — duplicates and equal bounds need a policy (usually strict <).
Real example & use case
Validating an in-memory price-band index tree before serving quotes.
Pros & cons
Pros: O(n) range DFS is robust. Cons: easy off-by-one on inclusive bounds.
Code example
def is_valid_bst(root) -> bool:
def dfs(node, low, high) -> bool:
if not node:
return True
if not (low < node.val < high):
return False
return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
return dfs(root, float('-inf'), float('inf'))Practice code · python (view only · no execution)
def is_valid_bst(root) -> bool:
def dfs(node, low, high) -> bool:
if not node:
return True
if not (low < node.val < high):
return False
return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
return dfs(root, float('-inf'), float('inf'))