# LeetCode 98: Validate Binary Search Tree

## Problem Restatement

We are given the root of a binary tree.

We need to return whether the tree is a valid binary search tree.

A valid binary search tree has three rules:

| Rule | Meaning |
|---|---|
| Left subtree | Every node must be strictly less than the current node |
| Right subtree | Every node must be strictly greater than the current node |
| Recursive rule | Both left and right subtrees must also be valid BSTs |

The word strictly matters. Duplicate values are not allowed in a valid BST for this problem.

The official problem asks us to determine whether a binary tree is a valid BST, where the left subtree contains only keys strictly less than the node key, the right subtree contains only keys strictly greater than the node key, and both subtrees must also be BSTs.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | `True` if the tree is a valid BST, otherwise `False` |
| Left rule | All values in the left subtree must be less than the root value |
| Right rule | All values in the right subtree must be greater than the root value |
| Duplicate values | Invalid |

Function shape:

```python
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        ...
```

## Examples

Example 1:

```python
root = [2, 1, 3]
```

Tree:

```python
    2
   / \
  1   3
```

The left value `1` is less than `2`.

The right value `3` is greater than `2`.

Answer:

```python
True
```

Example 2:

```python
root = [5, 1, 4, None, None, 3, 6]
```

Tree:

```python
    5
   / \
  1   4
     / \
    3   6
```

The node `4` is in the right subtree of `5`.

Every node in the right subtree of `5` must be greater than `5`.

But `4 < 5`.

Answer:

```python
False
```

## First Thought: Check Each Parent and Child

A tempting idea is to check only direct children.

For each node:

```python
left child < node < right child
```

This catches simple invalid trees, but it misses deeper violations.

Example:

```python
    5
   / \
  1   6
     / \
    3   7
```

Each direct parent-child comparison looks fine around node `6`:

```python
3 < 6 < 7
```

But `3` is inside the right subtree of `5`, so it must be greater than `5`.

Since `3 < 5`, the tree is invalid.

So each node needs more than its parent value. It needs a valid range.

## Key Insight

Every node has a lower bound and an upper bound.

For the root, the range is unbounded:

```python
(-infinity, infinity)
```

If a node has value `x`, then:

| Child | New valid range |
|---|---|
| Left child | `(lower, x)` |
| Right child | `(x, upper)` |

For example:

```python
    5
   / \
  1   6
     / \
    3   7
```

When we enter the right subtree of `5`, every node must be in:

```python
(5, infinity)
```

So when we reach `3`, it fails because:

```python
3 <= 5
```

## Algorithm

Define a recursive function:

```python
dfs(node, low, high)
```

It returns whether every node in this subtree is strictly inside the range:

```python
low < node.val < high
```

At each node:

1. If `node` is `None`, return `True`.
2. If `node.val <= low`, return `False`.
3. If `node.val >= high`, return `False`.
4. Validate the left subtree with upper bound `node.val`.
5. Validate the right subtree with lower bound `node.val`.

The final call is:

```python
dfs(root, -inf, inf)
```

## Walkthrough

Use:

```python
root = [5, 1, 4, None, None, 3, 6]
```

Start at `5`.

Valid range:

```python
(-inf, inf)
```

`5` is valid.

Go left to `1`.

New range:

```python
(-inf, 5)
```

`1` is valid.

Go right to `4`.

New range:

```python
(5, inf)
```

The value `4` violates the lower bound.

```python
4 <= 5
```

So the algorithm returns:

```python
False
```

## Correctness

The algorithm maintains this invariant:

For every recursive call `dfs(node, low, high)`, all nodes in this subtree must have values strictly between `low` and `high`.

The root starts with no real limits, so the invariant is true at the beginning.

When the algorithm moves to the left child of a node with value `x`, every value in that left subtree must be less than `x`, while still respecting the old lower bound. So the new range becomes `(low, x)`.

When the algorithm moves to the right child, every value in that right subtree must be greater than `x`, while still respecting the old upper bound. So the new range becomes `(x, high)`.

If any node falls outside its allowed range, the BST property is violated, and the algorithm returns `False`.

If every node satisfies its range, then every left subtree contains only smaller values, every right subtree contains only greater values, and this holds recursively. Therefore, the tree is a valid BST.

## Complexity

Let:

```python
n = number of nodes
h = height of the tree
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is checked once |
| Space | `O(h)` | Recursion stack depth equals tree height |

In the worst case, a skewed tree has height `n`.

In a balanced tree, the height is `O(log n)`.

## Implementation

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode], low: float, high: float) -> bool:
            if node is None:
                return True

            if node.val <= low or 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"))
```

## Code Explanation

The helper receives a node and its valid range:

```python
def dfs(node, low, high):
```

An empty subtree is valid:

```python
if node is None:
    return True
```

The value must be strictly between the bounds:

```python
if node.val <= low or node.val >= high:
    return False
```

Then validate both children.

For the left child, the upper bound becomes the current value:

```python
dfs(node.left, low, node.val)
```

For the right child, the lower bound becomes the current value:

```python
dfs(node.right, node.val, high)
```

The root starts with infinite bounds:

```python
return dfs(root, float("-inf"), float("inf"))
```

## Alternative: Inorder Traversal

A valid BST produces a strictly increasing sequence under inorder traversal.

So another solution is:

1. Traverse left subtree.
2. Visit current node.
3. Traverse right subtree.
4. Ensure each visited value is greater than the previous value.

```python
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None

        def inorder(node: Optional[TreeNode]) -> bool:
            nonlocal prev

            if node is None:
                return True

            if not inorder(node.left):
                return False

            if prev is not None and node.val <= prev:
                return False

            prev = node.val

            return inorder(node.right)

        return inorder(root)
```

This is also `O(n)` time and `O(h)` space.

The bounds method is often easier to reason about because it directly enforces the global BST constraints.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.isValidBST(root) is True

    root = TreeNode(
        5,
        TreeNode(1),
        TreeNode(4, TreeNode(3), TreeNode(6)),
    )
    assert s.isValidBST(root) is False

    root = TreeNode(1, TreeNode(1), None)
    assert s.isValidBST(root) is False

    root = TreeNode(5, TreeNode(4), TreeNode(6, TreeNode(3), TreeNode(7)))
    assert s.isValidBST(root) is False

    root = TreeNode(0)
    assert s.isValidBST(root) is True

    root = TreeNode(2, TreeNode(1), TreeNode(2))
    assert s.isValidBST(root) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[2, 1, 3]` | Valid simple BST |
| `[5, 1, 4, null, null, 3, 6]` | Main invalid example |
| Duplicate on left | Duplicates are invalid |
| Deep violation | Catches global range violation |
| Single node | Always valid |
| Duplicate on right | Strict inequality required |