practice · medium · from Binary Search Trees

Validate Binary Search Tree

time: O(n)
space: O(h)
tags: bst · recursion · dfs

in the wild Sanity-check a freshly deserialized index, or an in-place tree that you've just rotated — does the BST invariant still hold?

Problem

Given the root of a binary tree, decide whether it's a valid binary search tree:

The left subtree of every node contains only keys strictly less than that node's key.
The right subtree of every node contains only keys strictly greater than that node's key.
Both subtrees must themselves be BSTs.

Return true or false.

Examples

      2
     / \           → true
    1   3

      5
     / \           → false   (the 3 in the right subtree
    1   4                    violates "right subtree > 5")
        / \
       3   6

   (single node)   → true
   (empty tree)    → true

Why this is the canonical "invariant must hold globally" problem

The seductive wrong answer: at each node, just check node.left.val < node.val < node.right.val. That's a local check, and it fails on this tree:

       5
      / \
     1   6
        / \
       3   7      ← 3 is in 5's right subtree but 3 < 5!

Every node passes the local check, but the BST invariant is violated. The fix: at every node, check that its value lies in some (min, max) window that's tightened as you recurse. The root starts with (-∞, +∞); recursing left tightens the upper bound to the current node; recursing right tightens the lower bound.

This is the first place in a tree curriculum where you see the "passes context down, not just up" pattern — the opposite of diameter, which passes a single value up. Many tree problems mix the two; getting both right is what distinguishes a memorized algorithm from understanding.

Alternative: an in-order traversal of a valid BST yields a strictly increasing sequence — verify that on the fly with one previous-value variable.

Hints

Hint 1 — why local-only fails

Construct a small tree where every node individually satisfies left<n<right, but the BST invariant globally fails. (Hint: a value deep in the right subtree that's smaller than the root.) That counterexample tells you what the check is missing.

Hint 2 — window approach

Carry a (lo, hi) exclusive window into the recursion. At the root, (lo, hi) = (-∞, +∞). A node n is valid iff lo < n.val < hi. When recursing left, the new window is (lo, n.val). When recursing right, (n.val, hi).

Hint 3 — alternative: in-order traversal

A BST's in-order traversal is strictly increasing. So: traverse in-order, keep a "previous value" variable, return false the moment you see prev ≥ current. This avoids the explicit window — and naturally extends to "kth smallest", "find a pair summing to k in a BST", etc.

Solution

from dataclasses import dataclass
from typing import Optional
import math

@dataclass
class Node:
    val: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def is_valid_bst(root: Optional[Node]) -> bool:
    def go(n: Optional[Node], lo: float, hi: float) -> bool:
        if n is None:
            return True
        if not (lo < n.val < hi):
            return False
        return go(n.left, lo, n.val) and go(n.right, n.val, hi)
    return go(root, -math.inf, math.inf)

# Test cases
t1 = Node(2, Node(1), Node(3))
t2 = Node(5, Node(1), Node(4, Node(3), Node(6)))   # invalid
t3 = Node(5, Node(1), Node(6, Node(3), Node(7)))   # invalid (3 < 5 in right subtree)
t4 = Node(1)
t5 = None
cases = [(t1, True), (t2, False), (t3, False), (t4, True), (t5, True)]
for root, expected in cases:
    got  = is_valid_bst(root)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} is_valid_bst(...) = {got}  (expected {expected})")

class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function isValidBst(root) {
  function go(n, lo, hi) {
    if (n === null) return true;
    if (!(n.val > lo && n.val < hi)) return false;
    return go(n.left, lo, n.val) && go(n.right, n.val, hi);
  }
  return go(root, -Infinity, Infinity);
}

const t1 = new Node(2, new Node(1), new Node(3));
const t2 = new Node(5, new Node(1), new Node(4, new Node(3), new Node(6)));
const t3 = new Node(5, new Node(1), new Node(6, new Node(3), new Node(7)));
const t4 = new Node(1);
const t5 = null;
const cases = [[t1, true], [t2, false], [t3, false], [t4, true], [t5, true]];
for (const [root, expected] of cases) {
  const got = isValidBst(root);
  console.log(`${got === expected ? "✓" : "✗"} isValidBst(...) = ${got}  (expected ${expected})`);
}

pub struct Node {
    pub val:   i32,
    pub left:  Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

pub fn is_valid_bst(root: &Option<Box<Node>>) -> bool {
    // Use Option<i32> bounds so we can encode -∞ and +∞ without sentinel hacks.
    fn go(n: &Option<Box<Node>>, lo: Option<i32>, hi: Option<i32>) -> bool {
        let Some(n) = n else { return true; };
        if let Some(lo) = lo { if n.val <= lo { return false; } }
        if let Some(hi) = hi { if n.val >= hi { return false; } }
        go(&n.left, lo, Some(n.val)) && go(&n.right, Some(n.val), hi)
    }
    go(root, None, None)
}

fn leaf(v: i32) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: None, right: None }))
}
fn node(v: i32, l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: l, right: r }))
}

fn main() {
    let t1 = node(2, leaf(1), leaf(3));
    let t2 = node(5, leaf(1), node(4, leaf(3), leaf(6)));    // invalid
    let t3 = node(5, leaf(1), node(6, leaf(3), leaf(7)));    // invalid
    let t4 = leaf(1);
    let t5: Option<Box<Node>> = None;
    let cases = [(&t1, true), (&t2, false), (&t3, false), (&t4, true), (&t5, true)];
    for (root, expected) in cases {
        let got  = is_valid_bst(root);
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} is_valid_bst(...) = {}  (expected {})", got, expected);
    }
}

#include <iostream>
#include <limits>
#include <optional>

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

// long is large enough to hold INT_MIN-1 and INT_MAX+1 — used as sentinels.
bool go(Node* n, long lo, long hi) {
    if (!n) return true;
    if (n->val <= lo || n->val >= hi) return false;
    return go(n->left, lo, n->val) && go(n->right, n->val, hi);
}

bool is_valid_bst(Node* root) {
    return go(root,
              (long)std::numeric_limits<int>::min() - 1,
              (long)std::numeric_limits<int>::max() + 1);
}

int main() {
    Node* t1 = new Node(2, new Node(1), new Node(3));
    Node* t2 = new Node(5, new Node(1), new Node(4, new Node(3), new Node(6)));
    Node* t3 = new Node(5, new Node(1), new Node(6, new Node(3), new Node(7)));
    Node* t4 = new Node(1);
    Node* t5 = nullptr;
    std::pair<Node*, bool> cases[] = { {t1, true}, {t2, false}, {t3, false}, {t4, true}, {t5, true} };
    for (auto& [root, expected] : cases) {
        bool got = is_valid_bst(root);
        std::cout << (got == expected ? "✓" : "✗")
                  << " is_valid_bst(...) = " << (got ? "true" : "false")
                  << "  (expected " << (expected ? "true" : "false") << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

typedef struct Node {
    int          val;
    struct Node* left;
    struct Node* right;
} Node;

// long carries INT_MIN-1 / INT_MAX+1 sentinels safely on 64-bit.
static bool go(Node* n, long lo, long hi) {
    if (!n) return true;
    if (n->val <= lo || n->val >= hi) return false;
    return go(n->left, lo, n->val) && go(n->right, n->val, hi);
}

bool is_valid_bst(Node* root) {
    return go(root, (long)INT_MIN - 1, (long)INT_MAX + 1);
}

static Node* mk(int v, Node* l, Node* r) {
    Node* n = malloc(sizeof(Node));
    n->val = v; n->left = l; n->right = r;
    return n;
}

int main(void) {
    Node* t1 = mk(2, mk(1, NULL, NULL), mk(3, NULL, NULL));
    Node* t2 = mk(5, mk(1, NULL, NULL), mk(4, mk(3, NULL, NULL), mk(6, NULL, NULL)));
    Node* t3 = mk(5, mk(1, NULL, NULL), mk(6, mk(3, NULL, NULL), mk(7, NULL, NULL)));
    Node* t4 = mk(1, NULL, NULL);
    Node* t5 = NULL;
    printf("%s is_valid_bst(t1) = %s\n", is_valid_bst(t1) == true  ? "✓" : "✗", is_valid_bst(t1) ? "true" : "false");
    printf("%s is_valid_bst(t2) = %s\n", is_valid_bst(t2) == false ? "✓" : "✗", is_valid_bst(t2) ? "true" : "false");
    printf("%s is_valid_bst(t3) = %s\n", is_valid_bst(t3) == false ? "✓" : "✗", is_valid_bst(t3) ? "true" : "false");
    printf("%s is_valid_bst(t4) = %s\n", is_valid_bst(t4) == true  ? "✓" : "✗", is_valid_bst(t4) ? "true" : "false");
    printf("%s is_valid_bst(t5) = %s\n", is_valid_bst(t5) == true  ? "✓" : "✗", is_valid_bst(t5) ? "true" : "false");
    return 0;
}

idle

The trickiest part isn't the algorithm — it's handling ±∞. Python has math.inf; JS has Infinity; Rust models it with Option<i32>; C and C++ widen to long so INT_MIN − 1 and INT_MAX + 1 are representable. Pick whichever style your language makes cleanest.

Complexity

Time: O(n) — each node is visited once, O(1) work per node.
Space: O(h) recursion stack, where h is the tree height.
vs in-order approach: Same big-O. The in-order method has the nice property of failing as soon as it finds the first out-of-order pair, which can short-circuit faster in practice.

In the wild

Index corruption checks. A database's B-tree or BST index can be silently broken by power failure mid-write; validation runs on recovery to detect this.
Tree rotation testing. Whenever you implement AVL / Red-Black / Splay rotations, the unit tests run a "is the result still a BST" check after every operation. See the balanced trees lesson.
Compiler-generated lookup tables. Some compilers build sorted constant tables and embed them as BSTs; a validator catches a bug in the table-builder.

Variations

Validate "≤" instead of "<" (duplicates allowed in the right subtree). Adjust the strict inequalities to non-strict on one side. Beware of double-equality bugs.
Validate an AVL tree. BST check plus balance check (every node's two subtree heights differ by ≤ 1). Combine both into one O(n) pass.
Find the first violation. Return the offending node (or pair) rather than just a boolean — useful for diagnostic tools.
Validate a max-heap. Different invariant: every parent ≥ both children. Same recursion shape, different test.