Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    MediumTrees

    Validate Binary Search Tree

    Given the root of a binary tree, determine if it is a valid binary search tree (BST).

    A valid BST is defined as follows: the left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees.

    Example 1

    Input: root = [2,1,3]

    Output: true

    Example 2

    Input: root = [5,1,4,null,null,3,6]

    Output: false

    Explanation: The root node's value is 5, but its right child's value is 4.

    Constraints

    • The number of nodes in the tree is in the range [1, 10^4].
    • -2^31 <= Node.val <= 2^31 - 1
    View original on LeetCode ↗

    Checking that a node’s value is between its immediate parent and immediate children is not enough — a node can be locally fine but violate the BST property against a grandparent further up (e.g. [5,1,4,null,null,3,6]: 4 < 5, satisfying the local check against 5, but 4 is in 5’s right subtree, where everything must be > 5). Every node needs to satisfy a valid (low, high) range inherited from all its ancestors, not just its parent.

    Recursive with Range Bounds

    OptimalTime O(n)Space O(h)

    Carry down the open interval (low, high) that a node’s value must fall strictly inside. Going left tightens the upper bound to the parent’s value; going right tightens the lower bound.

    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: TreeNode | None) -> bool:
            def valid(node: TreeNode | None, low: float, high: float) -> bool:
                if node is None:
                    return True
                if not (low < node.val < high):
                    return False
                return valid(node.left, low, node.val) and valid(node.right, node.val, high)
    

            return valid(root, float("-inf"), float("inf"))

    Play the range pass on root = [5,1,6,null,null,3,7]. Unlike the earlier [5,1,4,null,null,3,6], every node here passes the check against its immediate parent, yet the tree is still invalid because node 3 breaks the lower bound it inherits from the root. Watch which (low, high) interval each node receives and which node finally rejects it.

    checking5against (−∞, +∞)inside range valid ✓

    Inherited range per node — both endpoints tighten as we descend

    5(−∞, +∞)
    1· · ·
    6· · ·
    3· · ·
    7· · ·
    1 / 6
    currentresultdiscarded
    not yet reached

    Root 5 is checked against (−∞, +∞) and passes. Its left child inherits upper bound 5; its right child inherits lower bound 5.

    Complexity: each node is visited once with O(1) comparison work → O(n) time. Recursion depth → O(h) space.

    Iterative Inorder Traversal

    Time O(n)Space O(h)

    A BST’s inorder traversal visits values in strictly increasing order if and only if the tree is valid. Walking that traversal with an explicit stack and comparing each value to the previous one avoids ever needing range bounds at all.

    class Solution:
        def isValidBST(self, root: TreeNode | None) -> bool:
            stack = []
            prev = float("-inf")
            node = root
            while stack or node:
                while node:
                    stack.append(node)
                    node = node.left
                node = stack.pop()
                if node.val <= prev:
                    return False
                prev = node.val
                node = node.right
            return True

    Why consider this: same O(n) time and O(h) space as the range-bound version, but it reframes the problem as a single linear scan with one running comparison instead of tracking two bounds per call. Some find this the more intuitive mental model once the “inorder = sorted” property of BSTs is internalized.

    More Trees practice