# Validate Binary Search Tree

- **Canonical ID**: `validate-binary-search-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/validate-binary-search-tree
- **Difficulty**: medium
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/validate-binary-search-tree/

## 1. Core Invariant / The Trick

Propagate an open validity interval `(lo, hi)` down the recursion: moving left narrows upper bound to `node.val`, moving right narrows lower bound to `node.val`. Strictly enforce `lo < node.val < hi`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(H)`
- **Proof**: Checks every node against exact ancestral upper/lower constraints once in pre-order DFS.

## 3. Minimal Idiomatic Code

### Python
```python
def isValidBST(root: Optional[TreeNode]) -> bool:
    def valid(node, lo, hi):
        if not node:
            return True
        if not (lo < node.val < hi):
            return False
        return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)
    return valid(root, float('-inf'), float('inf'))
```

### TypeScript
```typescript
export function isValidBST(root: TreeNode | null): boolean {
  const valid = (node: TreeNode | null, lo: number, hi: number): boolean => {
    if (!node) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return valid(node.left, lo, node.val) && valid(node.right, node.val, hi);
  };
  return valid(root, -Infinity, Infinity);
}
```

### C++
```cpp
bool valid(TreeNode* n, long long lo, long long hi) {
    if (!n) return true;
    if (n->val <= lo || n->val >= hi) return false;
    return valid(n->left, lo, n->val) && valid(n->right, n->val, hi);
}
bool isValidBST(TreeNode* root) { return valid(root, LLONG_MIN, LLONG_MAX); }
```

### Java
```java
boolean valid(TreeNode n, long lo, long hi) {
    if (n == null) return true;
    if (n.val <= lo || n.val >= hi) return false;
    return valid(n.left, lo, n.val) && valid(n.right, n.val, hi);
}
boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); }
```

### Go
```go
func isValidBST(root *TreeNode) bool {
    var valid func(*TreeNode, int64, int64) bool
    valid = func(n *TreeNode, lo, hi int64) bool {
        if n == nil { return true }
        v := int64(n.Val)
        if v <= lo || v >= hi { return false }
        return valid(n.Left, lo, v) && valid(n.Right, v, hi)
    }
    return valid(root, math.MinInt64, math.MaxInt64)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Only checking `left.val < node.val < right.val` misses invalid deep right-left grandchildren (e.g., `6` in left subtree of `5`).
- Using 32-bit `INT_MIN`/`INT_MAX` sentinels breaks on extreme leaf values; use `int64` / `float("inf")` / nullable bounds.

### Follow-ups
- Iterative inorder traversal checking strictly increasing previous value runs in the same time/space.