Validate Binary Search Tree

Ishaan S Published 24 Oct, 2026

Given the root of a binary tree, return true if it is a valid binary search tree (BST) and false otherwise.

A tree is a valid BST when, for every node:

every value in its left subtree is strictly smaller than the node's value,
every value in its right subtree is strictly larger than the node's value, and
both subtrees are themselves valid BSTs.

Equal values are therefore not allowed anywhere in the tree. The tree is given in level order with null for missing children.

Example 1

Input: root = [6,3,9,1,4,7,12] Output: true Why: Every subtree respects the ordering: 1 < 3 < 4 < 6 < 7 < 9 < 12.

Example 2

Input: root = [8,3,10,null,null,7,12] Output: false Why: 7 is a correct left child of 10, but it sits in the right subtree of the root 8, so it must be larger than 8.

Example 3

Input: root = [4,4] Output: false Why: The left child equals its parent, and the rule requires strictly smaller.

Constraints

The number of nodes is between 1 and 10⁴.
-2³¹ <= Node.val <= 2³¹ - 1
The tree height is at most 300.

Pattern Path · Binary Search Trees · problem 100 of 169

Checking only that each node is greater than its left child and smaller than its right child is not enough. Find a small tree where that local check passes but the tree is invalid.

Every node must lie in an allowed range determined by all its ancestors, not just its parent.

Recurse with bounds: the root may take any value; going left tightens the upper bound to the parent's value, going right tightens the lower bound.

Alternative view: an in-order traversal of a valid BST produces a strictly increasing sequence.

Target: O(n) time, O(h) recursion depth, h = tree height extra space.

Start simple

For every node, scan its entire left and right subtrees and compare all values with it: O(n²) in the worst case (O(n log n) for balanced trees).

The key idea

The BST property is about whole subtrees, not just children. A node deep on the right side of the root must be larger than the root, even if it is the left child of its own parent. So each node has an allowed open interval (low, high) inherited from its ancestors.

Start at the root with no limits. When you step into the left child, everything there must stay below the current value, so the new interval is (low, node.val). Stepping right gives (node.val, high). A node outside its interval breaks the property; if every node lies inside its interval, every ancestor's condition holds, because the interval is exactly the intersection of all the constraints its ancestors impose.

Use "no bound" (None / null or infinities) instead of integer sentinels, because node values may be the smallest or largest 32-bit integers. Each node is visited once, so the check is linear. Equivalent alternative: traverse in order and verify each value is strictly greater than the previous one.

Complexity

Time: O(n)
Space: O(h) recursion depth, h = tree height

Python

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, low, high):
            # Every value in this subtree must lie strictly between low and high
            # (None means "no limit on this side").
            if node is None:
                return True
            if low is not None and node.val <= low:
                return False
            if high is not None and node.val >= high:
                return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, None, None)

JavaScript

var isValidBST = function(root) {
  // Every value in this subtree must lie strictly between low and high
  // (null means "no limit on this side").
  const valid = (node, low, high) => {
    if (node === null) return true;
    if (low !== null && node.val <= low) return false;
    if (high !== null && node.val >= high) return false;
    return valid(node.left, low, node.val) && valid(node.right, node.val, high);
  };
  return valid(root, null, null);
};

What the interviewer is checking

The interviewer wants to see whether you catch the classic trap (checking only parent-child pairs) and can explain why ranges or in-order traversal capture the full definition.

Mistakes to avoid

Comparing a node only with its direct children.
Allowing equal values (<= instead of <).
Using INT_MIN / INT_MAX as initial bounds, which wrongly rejects trees that contain those exact values.
In the in-order approach, initialising prev to a number instead of "none yet".

Follow-ups to expect

Can you do it iteratively? (In-order traversal with an explicit stack.)
How would you find the two swapped nodes in a broken BST? (In-order, find the inversions.)
What if duplicates were allowed on one side? (Make that bound inclusive.)

In real software

Databases and in-memory ordered maps keep search trees whose ordering invariant must hold for lookups to be correct; consistency checkers walk the tree with exactly these range bounds.

Practice next

import java.util.*;

/** Definition for a binary tree node. */
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return false;
    }
}

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            TreeNode n = q.poll();
            if (i < a.length && a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{6, 3, 9, 1, 4, 7, 12});
        System.out.println(new Solution().isValidBST(root)); // true
    }
}

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return false;
    }
};

// Builds a tree from a level-order array (nullopt = missing child).
TreeNode* build(const vector<optional<int>>& a) {
    if (a.empty() || !a[0]) return nullptr;
    TreeNode* root = new TreeNode(*a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (i < a.size() && a[i]) { n->left = new TreeNode(*a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i]) { n->right = new TreeNode(*a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

int main() {
    TreeNode* root = build({6, 3, 9, 1, 4, 7, 12});
    cout << boolalpha << Solution().isValidBST(root) << endl;  // true
}

Topics #100 #t-bst Binary Search Tree DFS Medium Practice Tree