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:

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

Function shape:

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

Examples

Example 1:

root = [2, 1, 3]

Tree:

    2
   / \
  1   3

The left value 1 is less than 2.

The right value 3 is greater than 2.

Answer:

True

Example 2:

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

Tree:

    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:

False

First Thought: Check Each Parent and Child

A tempting idea is to check only direct children.

For each node:

left child < node < right child

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

Example:

    5
   / \
  1   6
     / \
    3   7

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

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:

(-infinity, infinity)

If a node has value x, then:

For example:

    5
   / \
  1   6
     / \
    3   7

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

(5, infinity)

So when we reach 3, it fails because:

3 <= 5

Algorithm

Define a recursive function:

dfs(node, low, high)

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

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:

dfs(root, -inf, inf)

Walkthrough

Use:

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

Start at 5.

Valid range:

(-inf, inf)

5 is valid.

Go left to 1.

New range:

(-inf, 5)

1 is valid.

Go right to 4.

New range:

(5, inf)

The value 4 violates the lower bound.

4 <= 5

So the algorithm returns:

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:

n = number of nodes
h = height of the tree

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

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

Implementation

# 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:

def dfs(node, low, high):

An empty subtree is valid:

if node is None:
    return True

The value must be strictly between the bounds:

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:

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

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

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

The root starts with infinite bounds:

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.

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

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: