DSA Guide
Trees

Validate Binary Search Tree

Check that a tree is a valid BST, and understand why comparing each node to its parent is not enough

MediumDFS· bounds passed down
TreeDFSBSTRecursion
Problem #98

Problem Statement

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

A valid BST requires:

  • Every node in the left subtree is strictly less than the node.
  • Every node in the right subtree is strictly greater than the node.
  • Both subtrees are themselves valid BSTs.
Input:  root = [2, 1, 3]
Output: true

Input:  root = [5, 1, 4, null, null, 3, 6]
Output: false
Why:    4 is in 5's right subtree, but 4 < 5

Intuition

The obvious first attempt is to check each node against its parent:

if node.left:  assert node.left.val  < node.val
if node.right: assert node.right.val > node.val

This is wrong, and the counterexample is the whole lesson of the problem.

The tree that breaks the naive check

      5
     / \
    1   7
       / \
      3   9        ← 3 is less than 5, but sits in 5's RIGHT subtree

Check every parent–child pair and each one passes: 1 < 5, 7 > 5, 3 < 7, 9 > 7.

But this is not a BST. Searching for 3 starts at 5, sees 3 < 5, and goes left — into a subtree that does not contain it. The tree lies about where its values are.

The naive check fails because the BST rule is not about parents. Read it again: every node in the left subtree, not the left child.

The key insight

A node's legal range is decided by every ancestor above it, not just its parent.

Going left tightens the ceiling. Going right raises the floor. So carry a (low, high) window down the tree, and check each node fits inside it.

How the window narrows

Start at the root with no constraints at all: (-∞, +∞).

MoveWhat it meansNew window
Go left from node vEverything here must be < v(low, v)
Go right from node vEverything here must be > v(v, high)

Trace the broken tree above:

5   window (-inf, +inf)   ok
├─ left  1   window (-inf, 5)   ok    1 < 5
└─ right 7   window (5, +inf)   ok    7 > 5
   ├─ left  3   window (5, 7)   FAIL  3 is not > 5
   └─ right 9   window (7, +inf) ok

Node 3 is caught. Its parent said "less than 7", but its grandparent had already said "greater than 5", and 3 cannot satisfy both.

Approach

Start with an unbounded window

The root may hold any value, so begin with low = -∞ and high = +∞.

Reject a node outside its window

If node.val <= low or node.val >= high, the tree is invalid. Both comparisons are strict — duplicates are not allowed.

Tighten and recurse left

The left subtree keeps the same floor but takes this node as its new ceiling: (low, node.val).

Tighten and recurse right

The right subtree takes this node as its new floor and keeps the ceiling: (node.val, high).

Valid only if both sides are valid

An empty subtree is trivially valid, which gives the base case for free.

Watch it run

root = [5, 1, 7, null, null, 3, 9] — the tree that fools the naive check
51739
low-infhigh+inf
The root may be anything. It passes.
1 / 5
The floor of 5 was set by the root and survived two levels of descent.

Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def is_valid_bst(root: TreeNode | None) -> bool:
    """Check the BST property by carrying an allowed range down the tree."""

    def check(node: TreeNode | None, low: float, high: float) -> bool:
        # An empty subtree breaks no rules.
        if node is None:
            return True

        # Strict comparisons: equal values are not allowed in a BST.
        if not (low < node.val < high):
            return False

        # Going left lowers the ceiling; going right raises the floor.
        return check(node.left, low, node.val) and check(node.right, node.val, high)

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


def is_valid_bst_inorder(root: TreeNode | None) -> bool:
    """Alternative: an inorder walk of a valid BST is strictly increasing."""
    previous: float = float("-inf")
    stack: list[TreeNode] = []
    node = root

    while stack or node:
        while node:
            stack.append(node)
            node = node.left

        node = stack.pop()

        # Must be strictly greater — equality means a duplicate.
        if node.val <= previous:
            return False
        previous = node.val

        node = node.right

    return True

The inorder alternative

An inorder walk (left, node, right) of a valid BST produces values in strictly increasing order. So a second correct solution is: walk inorder, and check each value is bigger than the last.

It needs only one variable instead of two bounds, but the comparison must be strict — <= catches duplicates, < would let them through.

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

  • Time — every node is visited once and compared against two bounds. The bounds version can exit early: it stops at the first violation, so a tree broken near the root costs far less than n.
  • Space — the recursion stack, one frame per level. O(log n) balanced, O(n) for a chain.

Edge Cases

Binary Tree Level Order Traversal

Visit a tree level by level with BFS, using the queue's size to know where each level ends

Lowest Common Ancestor of a BST

Find where two nodes' paths split, using the ordering of a BST to walk straight there without any searching

On this page

Problem StatementIntuitionHow the window narrowsApproachStart with an unbounded windowReject a node outside its windowTighten and recurse leftTighten and recurse rightValid only if both sides are validWatch it runSolutionComplexity AnalysisEdge CasesRelated Problems