DSAPrep
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"))

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

5
1
4
3
6
1 / 3
comparingseenresultdiscarded

Root 5 checked against (-inf, inf). Valid. Left subtree gets range (-inf, 5); right subtree gets (5, inf).

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.