Validate Binary Search Tree

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    Given the root of a binary tree, decide whether it is a valid binary search tree: for every node, all values in its left subtree are strictly smaller and all values in its right subtree are strictly larger. Duplicates are not allowed.

    The trap is in the word "all": comparing a node only with its children isn't enough. The fix is to pass down the range each node must fall in. Original problem: LeetCode 98.

    Example

    Both trees look locally ordered, but in the right one the 4 sits in the right subtree of 5, so it is not a valid BST.
    Both trees look locally ordered, but in the right one the 4 sits in the right subtree of 5, so it is not a valid BST.
    Input:  [5, 1, 7, null, null, 6, 8]
    Output: true
    Input:  [5, 1, 7, null, null, 4, 8]
    Output: false      # 4 is in 5's right subtree

    Constraints (assumed)

    • 1 ≤ nodes ≤ 10,000.
    • Values cover the full 32-bit integer range.

    What this question tests

    • Understanding that the BST rule is about whole subtrees, not just children.
    • Passing information down a recursion (bounds), not just returning it up.
    • Boundary care: strict inequality and values at the integer limits.

    Questions to ask first

    1. Are duplicates allowed, and on which side? (Here: no duplicates; equal values make it invalid.)
    2. What range can values take? Full 32-bit range means sentinels like INT_MIN are unsafe.
    3. Is an empty tree valid? (Yes.)
    4. Recursive is fine? Mention the iterative version for very deep trees.