#98 Validate Binary Search Tree

frequently reported atBloomberg Microsoft Amazon Meta Oracle Salesforce

the problem

In plain words

Return true if the tree is a valid BST: every left-subtree value is strictly less than the node, every right-subtree value strictly greater, and both subtrees are BSTs.

in root = [2,1,3]

out true

in root = [5,1,4,null,null,3,6]

out false

4 is in 5's right subtree but 4 < 5.

1 ≤ number of nodes ≤ 10⁴
-2³¹ ≤ Node.val ≤ 2³¹ − 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (top-down)BST property

A node isn't constrained by its parent alone but by all its ancestors. Carry the tightest (low, high) range down the tree — or simply check that the inorder sequence is strictly increasing.

solutions

From brute force to optimal

A tree is a BST iff its inorder is strictly increasing.

Collect inorder values.
Check each value is greater than the previous.

timeO(n)

One traversal and one scan.

spaceO(n)

The whole list is stored.

javajava.util.*

1class Solution {2    public boolean isValidBST(TreeNode root) {3        List<Integer> values = new ArrayList<>();4        collect(root, values);5        for (int i = 1; i < values.size(); i++) {6            if (values.get(i - 1) >= values.get(i)) return false;   // must be STRICTLY increasing7        }8        return true;9    }10 11    private void collect(TreeNode node, List<Integer> out) {12        if (node == null) return;13        collect(node.left, out);14        out.add(node.val);15        collect(node.right, out);16    }17}

Each node must lie strictly inside the range set by its ancestors; going left lowers high, going right raises low.

valid(root, null, null).
Out of range → false.
Recurse left with (low, node.val) and right with (node.val, high).

timeO(n)

Each node checked once; stops early on the first violation.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    public boolean isValidBST(TreeNode root) {3        return valid(root, null, null);4    }5 6    /** Every value in this subtree must lie strictly between low and high (null = no limit). */7    private boolean valid(TreeNode node, Integer low, Integer high) {8        if (node == null) return true;9        if ((low != null && node.val <= low)10                || (high != null && node.val >= high)) return false;11        return valid(node.left, low, node.val)                           // left: new upper bound12                && valid(node.right, node.val, high);                    // right: new lower bound13    }14}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public boolean isValidBST(TreeNode root) {3        return valid(root, null, null);4    }5 6    /** Every value in this subtree must lie strictly between low and high (null = no limit). */7    private boolean valid(TreeNode node, Integer low, Integer high) {8        if (node == null) return true;9        if ((low != null && node.val <= low)10                || (high != null && node.val >= high)) return false;11        return valid(node.left, low, node.val)                           // left: new upper bound12                && valid(node.right, node.val, high);                    // right: new lower bound13    }14}

Same as the list idea, but only remember the previous value.

Iterative inorder with a stack.
If cur.val ≤ prev → false.
prev = cur.val.

timeO(n)

Each node pushed and popped once.

spaceO(h)

The stack holds one left spine.

javajava.util.*

1class Solution {2    public boolean isValidBST(TreeNode root) {3        Deque<TreeNode> stack = new ArrayDeque<>();4        TreeNode cur = root;5        Integer prev = null;                                   // last value visited in order6        while (cur != null || !stack.isEmpty()) {7            while (cur != null) { stack.push(cur); cur = cur.left; }8            cur = stack.pop();9            if (prev != null && cur.val <= prev) return false;   // order broken10            prev = cur.val;11            cur = cur.right;12        }13        return true;14    }15}

in the room

How to say it in the interview

talk track

Show the trap example [5,4,6,null,null,3,7] — it proves parent-only checks fail.
Explain why the bounds are Integer (nullable) and not int sentinels.

traps

Using Integer.MIN_VALUE/MAX_VALUE as initial bounds: a node equal to them is wrongly rejected. Use null or long.
Using < instead of <= in the check: duplicates must fail.

what they ask next

Follow-ups

Recover Binary Search Tree (LC 99) — two nodes were swapped?

Inorder and find the one or two places where order drops; swap the first big and the last small value back.

before you submit

Edge cases to test

Equal values → invalid: the order must be strict.
Nodes holding Integer.MIN_VALUE or MAX_VALUE → can still be valid; int sentinels would wrongly reject them.
A single node → valid.

practise next