Skip to content

Validate Bst

Problem

Given the root of a binary tree, determine if it is a valid BST. A valid BST requires every node's value to be strictly between the values of its ancestors that constrain it.

Approach

Recursive with min/max bounds. At each node, check that the value is within (lo, hi) and recurse with tightened bounds.

When to Use

Constraint propagation through a tree — "validate BST", "check ordering invariant". Pass tightening bounds (lo, hi) down the recursion. Also: range-constrained tree problems, interval checks.

Complexity
Time O(n)
Space O(h) where h = height of tree (call stack)

Implementation

validate_bst

Validate binary search tree.

Problem

Given the root of a binary tree, determine if it is a valid BST. A valid BST requires every node's value to be strictly between the values of its ancestors that constrain it.

Approach

Recursive with min/max bounds. At each node, check that the value is within (lo, hi) and recurse with tightened bounds.

When to use

Constraint propagation through a tree — "validate BST", "check ordering invariant". Pass tightening bounds (lo, hi) down the recursion. Also: range-constrained tree problems, interval checks.

Complexity

Time: O(n) Space: O(h) where h = height of tree (call stack)

is_valid_bst 

is_valid_bst(
    root: TreeNode | None,
    lo: float = float("-inf"),
    hi: float = float("inf"),
) -> bool

Return True if the binary tree rooted at root is a valid BST.

is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3))) True is_valid_bst(TreeNode(2, TreeNode(3), TreeNode(1))) False

Source code in src/algo/trees/validate_bst.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def is_valid_bst(
    root: TreeNode | None,
    lo: float = float("-inf"),
    hi: float = float("inf"),
) -> bool:
    """Return True if the binary tree rooted at `root` is a valid BST.

    >>> is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3)))
    True
    >>> is_valid_bst(TreeNode(2, TreeNode(3), TreeNode(1)))
    False
    """
    if not root:
        return True
    if not (lo < root.val < hi):
        return False
    return is_valid_bst(root.left, lo, root.val) and is_valid_bst(
        root.right, root.val, hi
    )
tests/trees/test_validate_bst.py
"""Tests for validate binary search tree."""

from algo.trees.validate_bst import TreeNode, is_valid_bst


class TestIsValidBST:
    def test_valid_bst(self) -> None:
        tree = TreeNode(2, TreeNode(1), TreeNode(3))
        assert is_valid_bst(tree) is True

    def test_invalid_bst(self) -> None:
        tree = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
        assert is_valid_bst(tree) is False

    def test_empty_tree(self) -> None:
        assert is_valid_bst(None) is True

    def test_single_node(self) -> None:
        assert is_valid_bst(TreeNode(0)) is True

    def test_equal_values_invalid(self) -> None:
        """BST requires strictly less/greater, not equal."""
        tree = TreeNode(1, TreeNode(1))
        assert is_valid_bst(tree) is False

    def test_deep_violation(self) -> None:
        """Value in left subtree exceeds the root."""
        #     5
        #    / \
        #   3   7
        #  / \
        # 2   6  <-- 6 > 5, violates BST
        tree = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(6)), TreeNode(7))
        assert is_valid_bst(tree) is False

    def test_valid_large_bst(self) -> None:
        #       8
        #      / \
        #     4   12
        #    / \  / \
        #   2  6 10 14
        tree = TreeNode(
            8,
            TreeNode(4, TreeNode(2), TreeNode(6)),
            TreeNode(12, TreeNode(10), TreeNode(14)),
        )
        assert is_valid_bst(tree) is True

Implement it yourself

Run: just challenge trees validate_bst

Then implement the functions to make all tests pass. Use just study trees for watch mode.

Reveal Solution

validate_bst

Validate binary search tree.

Problem

Given the root of a binary tree, determine if it is a valid BST. A valid BST requires every node's value to be strictly between the values of its ancestors that constrain it.

Approach

Recursive with min/max bounds. At each node, check that the value is within (lo, hi) and recurse with tightened bounds.

When to use

Constraint propagation through a tree — "validate BST", "check ordering invariant". Pass tightening bounds (lo, hi) down the recursion. Also: range-constrained tree problems, interval checks.

Complexity

Time: O(n) Space: O(h) where h = height of tree (call stack)

is_valid_bst 

is_valid_bst(
    root: TreeNode | None,
    lo: float = float("-inf"),
    hi: float = float("inf"),
) -> bool

Return True if the binary tree rooted at root is a valid BST.

is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3))) True is_valid_bst(TreeNode(2, TreeNode(3), TreeNode(1))) False

Source code in src/algo/trees/validate_bst.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def is_valid_bst(
    root: TreeNode | None,
    lo: float = float("-inf"),
    hi: float = float("inf"),
) -> bool:
    """Return True if the binary tree rooted at `root` is a valid BST.

    >>> is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3)))
    True
    >>> is_valid_bst(TreeNode(2, TreeNode(3), TreeNode(1)))
    False
    """
    if not root:
        return True
    if not (lo < root.val < hi):
        return False
    return is_valid_bst(root.left, lo, root.val) and is_valid_bst(
        root.right, root.val, hi
    )