linkjobai

Validate Binary Search Tree: Pass Bounds Down, Not Just Compare Children

Validate Binary Search Tree is a classic trap. Checking that each node is greater than its left child and smaller than its right child is not enough, because a node deep in the left subtree can still be larger than an ancestor.

The bounds idea

Every node must sit inside an open interval (low, high) inherited from its ancestors. Going left tightens high to the node value; going right tightens low.

def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if not root: return True
    if not (low < root.val < high): return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

The in-order alternative

An in-order traversal of a valid BST is strictly increasing, so you can track the previous value and fail on any non-increase. It is a nice second answer that shows you know the BST property from two angles.

Edge cases to raise

Ask whether duplicates are allowed and on which side. Mention that using None instead of infinity avoids overflow issues in languages with fixed-width integers. Recursion depth is the tree height, so a skewed tree may need an iterative stack.

More interview notes like this live at linkjob.ai. Disclosure: I help build Linkjob AI.