Validate Binary Search Tree

1. Problem & Core Objective

Return true if the tree is a valid BST. Valid means:

• every node in a node's left subtree is strictly less than it
• every node in its right subtree is strictly greater
• both subtrees are themselves valid BSTs

    5                    5
   / \                  / \
  1   4      false     4   6      false        2      true
     / \                  / \                 / \
    3   6                3   7               1   3

Constraints: 1 <= nodes <= 10^4 · -2^31 <= Node.val <= 2^31 - 1

What's actually being tested: whether you notice the condition is about subtrees, not about parent-child pairs. Comparing each node only with its immediate parent is the single most common wrong answer, and it passes a lot of casual tests.

The value range is also a deliberate trap — node values can be Integer.MIN_VALUE and MAX_VALUE.

2. First-Principles Thought Process

The local check is not enough

Consider this tree, where every parent-child comparison passes:

• 4 < 5 ✓ (left child smaller)
• 6 > 5 ✓ (right child larger)
• 3 < 6 ✓ (left child smaller)
• 7 > 6 ✓ (right child larger)

Every local check passes. But node 3 sits in the right subtree of 5, so it must be greater than 5 — and it isn't. Not a BST.

The definition says every node in the right subtree, not the right child. A node must beat its entire ancestry, not just its parent.

The fix: carry bounds down

Each node inherits a valid open interval (lo, hi) from its ancestors:

• Going left from a node tightens the upper bound: the child must be < node.val.
• Going right tightens the lower bound: the child must be > node.val.

valid(node, lo, hi):
    if node is null: return true
    if node.val <= lo or node.val >= hi: return false
    return valid(node.left,  lo, node.val)
       and valid(node.right, node.val, hi)

In the example: node 6 inherits (5, +∞) and passes. Node 3, being 6's left child, inherits (5, 6) — and 3 > 5 fails. Caught.

This is the downward information flow from question 10, carrying two values instead of one.

The other angle: inorder is sorted

A BST's inorder traversal produces values in strictly increasing order. So an equivalent check is: walk inorder, and verify each value exceeds the previous one.

Both are O(n). The bounds version short-circuits more naturally and doesn't need to remember a previous node across the recursion.

The overflow trap

Values can be Integer.MIN_VALUE or MAX_VALUE. If you seed the bounds with those, a legitimate node holding Integer.MIN_VALUE fails against lo = Integer.MIN_VALUE under a strict <= test.

Three fixes: use long bounds, use boxed Integer with null meaning "unbounded", or restructure to pass the ancestor nodes rather than values. I use long.

3. Solution Paths

Approach 1 — Compare each node with its children only (the wrong answer)

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (root.left  != null && root.left.val  >= root.val) return false;
    if (root.right != null && root.right.val <= root.val) return false;
    return isValidBST(root.left) && isValidBST(root.right);
}

• Time O(n) · Space O(h) · Correct: no

Counter-questions on this approach

⭐ "Give me an input where this fails."

[5,4,6,null,null,3,7]. Every parent-child comparison passes — 4 < 5, 6 > 5, 3 < 6, 7 > 6 — so this returns true. But 3 is in the right subtree of 5 and is less than 5, so it's not a BST.

The bug is reading the definition as a property of edges when it's a property of subtrees. A node constrains everything beneath it, not just its immediate children.

"Why does it pass so many tests?"

Because violations that are purely local are far more common in small hand-written examples than violations that only appear two levels down. It takes a deliberately constructed case to expose it, which is exactly why interviewers use this problem.

"Can it be patched without restructuring?"

Not meaningfully. You could compare each node against the max of its left subtree and the min of its right, but computing those at every node is O(n²) — the same redundancy as questions 3 and 4. Carrying bounds downward gets it in one pass.

Approach 2 — Carry bounds down (optimal)

public boolean isValidBST(TreeNode root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean valid(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;

    return valid(node.left,  lo, node.val)       // left: tighten the upper bound
        && valid(node.right, node.val, hi);      // right: tighten the lower bound
}

Trace — [5,4,6,null,null,3,7]:

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why long bounds instead of int?"

Because node values span the full int range. If I seeded with Integer.MIN_VALUE and a node legitimately held Integer.MIN_VALUE, the test node.val <= lo would be MIN_VALUE <= MIN_VALUE — true — and a valid single-node tree would be rejected.

long bounds sit strictly outside the int range, so no real value can ever tie with a sentinel. It's the same discipline as question 4's −1: verify the sentinel is outside the data's domain rather than assuming it.

⭐ "What are the alternatives to long?"

Boxed Integer bounds with null meaning unbounded, and explicit null checks: (lo != null && node.val <= lo). More verbose but works for any numeric type, including one already using the full long range.

Or pass the ancestor nodes rather than their values, which sidesteps sentinels entirely. long is the least code for int data, so I default to it and mention the others.

⭐ "Why strict <= and >= rather than < and >?"

Because BST validity here is strict — duplicates are not allowed. node.val <= lo rejects a node equal to a lower bound it must exceed. If the problem permitted duplicates on one side, exactly one of these would relax, and I'd ask which side.

"Why does the left child inherit hi = node.val rather than the parent's hi?"

Because it must satisfy both constraints: less than its parent, and still within whatever the ancestors allowed. Since node.val < hi already holds (the node passed its own check), node.val is the tighter of the two, so passing it is correct and sufficient.

"Does it short-circuit?"

Yes — && stops at the first invalid subtree, and the range check returns before recursing at all. A violation near the root exits almost immediately.

Approach 3 — Inorder traversal must be strictly increasing

private TreeNode prev = null;

public boolean isValidBST(TreeNode root) {
    prev = null;
    return inorder(root);
}

private boolean inorder(TreeNode node) {
    if (node == null) return true;

    if (!inorder(node.left)) return false;              // left
    if (prev != null && prev.val >= node.val) return false;   // node
    prev = node;
    return inorder(node.right);                          // right
}

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why is inorder the relevant traversal?"

Because inorder visits left subtree, node, right subtree — which for a BST is exactly ascending order. So "is this a BST" becomes "is this sequence strictly increasing", which needs only the previous value.

Preorder and postorder have no such property, so the trick is specific to inorder.

⭐ "Why keep a prev node rather than a prev value?"

To avoid the sentinel problem again. A prev value would need an initial "nothing seen yet" marker, and any int marker could collide with a real value. prev == null expresses "no previous node" unambiguously.

It's the boxed-Integer idea from above, applied by keeping the node reference instead.

"The mutable field makes it non-reentrant. Same objection as question 3?"

Yes, and I reset it at the start for the same reason. Alternatives: an explicit iterative inorder with a stack, which keeps prev as a local; or returning a record of (valid, min, max) from each subtree.

The iterative version is genuinely nice here, because it also short-circuits without unwinding recursion.

"Which do you prefer?"

The bounds version. It short-circuits more directly, needs no mutable state, and the bounds make the reason for failure visible. The inorder version is a good second answer and generalises to question 12, where you want the k-th element of that same increasing sequence.

Comparison

4. Why the Optimal Wins

The local check is wrong, not slow — it misreads a subtree property as an edge property.

Both correct approaches are O(n) time and O(h) space. The bounds version wins on directness: it states the invariant explicitly, short-circuits without extra machinery, and needs no mutable state carried across calls.

The framing worth keeping:

A BST constrains every node by its whole ancestry, not by its parent. Carry the interval (lo, hi) down: going left tightens hi, going right tightens lo.

And the sentinel discipline that keeps recurring: verify your sentinel lies outside the data's range. Here it doesn't, which is why the bounds must be long.

5. Java Prerequisites

Bounds as long

valid(root, Long.MIN_VALUE, Long.MAX_VALUE);

Necessary because node values can be Integer.MIN_VALUE / MAX_VALUE. Comparing an int against a long widens automatically — no cast needed.

Boxed alternative

private boolean valid(TreeNode n, Integer lo, Integer hi) {
    if (lo != null && n.val <= lo) return false;
    ...
}

Inorder with a previous pointer

if (prev != null && prev.val >= node.val) return false;
prev = node;

Keep the node, not the value, so null unambiguously means "nothing yet".

Reset instance fields in the public method, or a second call sees stale state.

6. Interview Communication Guide

Clarifying questions: Are duplicates allowed, and if so on which side (not here — it's strict)? What's the value range (full int — this forces long bounds)? Can the tree be empty (constraints say at least 1, but null is trivially valid)?

The pitch

"The important thing is that the BST property is about subtrees, not parent-child pairs. Every node in a node's right subtree must be greater than it — not just its right child.

So the naive check fails. Take [5,4,6,null,null,3,7]: 4 < 5, 6 > 5, 3 < 6, 7 > 6 — every local comparison passes. But 3 is in the right subtree of 5 and is smaller than 5, so it's not a BST.

The fix is to carry an allowed interval down the recursion. Every node inherits (lo, hi) from its ancestors and must fall strictly inside. Going left tightens the upper bound to the node's value; going right tightens the lower bound. So node 6 gets (5, +∞) and passes, and node 3 gets (5, 6) — and 3 > 5 fails.

One trap: values span the full int range, so I use long bounds. If I seeded with Integer.MIN_VALUE and a node legitimately held Integer.MIN_VALUE, the strict comparison would reject a valid tree. The sentinel has to lie outside the data's range.

O(n) time, O(h) stack.

There's an equivalent approach: a BST's inorder traversal is strictly increasing, so walk inorder and check each value against the previous. I'd keep the previous node rather than its value, so null cleanly means 'nothing seen yet'. That version is the natural lead-in to finding the k-th smallest element."

Edge cases to volunteer:

Name the third and fourth rows. The first catches parent-only comparison; the second catches int bounds. Together they're what separates a working solution from one that merely looks right.

7. Follow-Up Questions — Modified Constraints

⭐ "Allow duplicates on the left."

Relax exactly one comparison: node.val < lo instead of <=, so a node may equal its lower bound. I'd confirm which side duplicates go, since both conventions exist and the choice changes which comparison relaxes.

⭐ "Find the k-th smallest element."

Question 12. Inorder gives sorted order, so stop after k visits. The inorder approach here is the direct lead-in — which is why it's worth writing even though the bounds version is my preferred answer.

"Recover a BST where exactly two nodes were swapped."

LeetCode 99. Do the inorder walk and find where the increasing order breaks — there will be one or two such points. If two, swap the first node of the first break with the second node of the second; if one, swap the two nodes at that break. O(n) time, O(h) space, and Morris traversal makes it O(1).

"Count how many nodes violate the BST property."

Ambiguous, and worth saying so — removing one badly-placed node near the root can fix an entire subtree, so "number of violations" depends on how you attribute blame. I'd ask for a precise definition before implementing.

"Do it iteratively."

Either approach converts: a stack of (node, lo, hi) triples for the bounds version, or the standard iterative inorder with a stack for the other. Both are O(h) on the heap rather than the call stack, which matters at 10^4 nodes in a chain.

"Do it in O(1) space."

Morris inorder traversal — temporarily thread each node's rightmost-in-left-subtree back to it, walk, then unthread. O(n) time, O(1) space, at the cost of mutating the tree during traversal. Not thread-safe and not usable on an immutable tree, but it's the genuine answer to the O(1) question.