Validate Binary Search Tree: A Step-by-Step Interview Walkthrough

Validate Binary Search Tree is one of the great traps in the interview rotation. The problem looks like a five-line traversal, and most candidates write a five-line traversal that's almost right — passing every easy test case and failing one subtle one. The reason interviewers love it is that the wrong solution is genuinely tempting: "check that the left child is smaller and the right child is bigger" sounds like the definition of a BST, but it isn't. The real BST property is global, and the real challenge is figuring out how to enforce a global property using only local checks. Candidates who write the naive child-comparison solution learn the hard way that the BST invariant is stronger than it looks. Candidates who slow down and ask "what does every descendant need to satisfy?" arrive at the right answer cleanly.

Validating data-structure invariants is something production systems do constantly. Database engines check B-tree integrity after recovery. Filesystems verify directory ordering during repair. Compiler optimizers validate AST invariants after transformations. Concurrent data structures rerun consistency checks after lock-free updates. Any time a structure has rules that span more than just neighboring nodes, you need exactly the technique this problem teaches: pass constraints down a recursive traversal and enforce them at every level.

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree.

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with values strictly less than the node's value.

• The right subtree of a node contains only nodes with values strictly greater than the node's value.

• Both the left and right subtrees must also be binary search trees.

Return true if the tree is a valid BST, false otherwise.

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: the root of a binary tree (may be null).

Output: a boolean — true if the tree is a valid BST, false otherwise.

Details to clarify:

• Does the BST property apply only to direct children, or to the entire subtree? Entire subtree — this is the critical clarification.

• Are duplicates allowed? No — the inequality is strict. A node with value equal to an ancestor invalidates the tree.

• Is an empty tree valid? Yes.

• Can node values be very large or very small? Yes — they can reach Integer.MIN_VALUE and Integer.MAX_VALUE, which matters for how we initialize bounds.

The single most important question is the scope one. The naive interpretation — "check that the immediate left child is smaller and the immediate right child is bigger" — is wrong for this problem and is the trap interviewers are watching for.

2. Identify the Category of the Question

A few signals jump out:

• The input is a tree, and we need to traverse it.

• The validity rule isn't just local to each node — it applies across entire subtrees.

• The check at each node depends on context from its ancestors.

That combination — tree traversal with non-local constraints — points to a particular pattern: DFS that carries constraints down the recursion. Same family as "Lowest Common Ancestor with constraints," "Path Sum III," and other tree problems where each node's validity depends on what came above it.

3. Brute Force Solution — and Why It's a Trap

Let's try the most natural-looking solution and see why it fails. The BST definition says "left child smaller, right child bigger," so the obvious code is:

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

This passes a lot of test cases. It correctly catches a tree like:

    5
   / \
  6   8       (left child 6 >= root 5, invalid)

But consider this tree:

       10
      /  \
     5    15
         /  \
        6    20

Let's run the naive check. At node 10: left child 5 < 10 ✓, right child 15 > 10 ✓. At node 15: left child 6 < 15 ✓, right child 20 > 15 ✓. The algorithm returns true.

But the tree isn't a valid BST. The node 6 lives in node 10's right subtree, which means every value down there must be greater than 10. But 6 < 10. The naive check missed it because it only compared each node to its immediate parent — not to its ancestors further up.

This is the moment that should change how we think about the problem. The BST invariant isn't a property of adjacent pairs — it's a property of the entire ancestor chain. Every node has to satisfy constraints set not just by its parent, but by every ancestor on the path from the root. We need a way to track and enforce those accumulated constraints.

4. Brainstorm More Solutions

Step 1: What constraint does each node actually need to satisfy?

Let's think carefully about what's required of a node deep in the tree. Take the rogue 6 in the broken example above. The path from the root is 10 → 15 → 6. What had to be true for 6 to be a valid BST node at that position?

• It's in the right subtree of 10, so it has to be > 10.

• It's in the left subtree of 15, so it has to be < 15.

So the valid range for that position is (10, 15). The value 6 doesn't fall in that range, so the tree is invalid.

Notice what just happened. Each ancestor contributed one constraint to the valid range:

• Going left from 15 set the upper bound: anything below 15's left link must be < 15.

• Going right from 10 set the lower bound: anything below 10's right link must be > 10.

So as we walk down the tree, each step tightens either the lower bound or the upper bound. The node's allowed range shrinks as we descend. If we can track that range, we can check any node in O(1) against it.

Step 2: Design the recursion

Let's define a function validate(node, min, max) that returns true if the subtree rooted at node is a valid BST with all values strictly in the open interval (min, max).

The recursive structure:

1. Base case: if node is null, the empty subtree is trivially valid — return true.

2. Check the current node: if node.val <= min or node.val >= max, the value falls outside the allowed range — return false.

3. Recurse into children with tightened bounds:

   • The left subtree must contain values less than node.val, so its upper bound becomes node.val. The lower bound stays at min.

   • The right subtree must contain values greater than node.val, so its lower bound becomes node.val. The upper bound stays at max.

The initial call uses (-∞, +∞) because the root has no ancestors imposing constraints.

validate(node, min, max):
    if node is null: return true
    if node.val <= min or node.val >= max: return false
    return validate(node.left, min, node.val)
       and validate(node.right, node.val, max)

The recurrence is small but powerful. It expresses exactly the BST invariant — "every node falls within the range carved out by its ancestors" — in three lines.

Step 3: Watch out for integer boundary values

There's a subtle bug waiting in this solution. What if a node's value is Integer.MIN_VALUE or Integer.MAX_VALUE?

Suppose the root is Integer.MIN_VALUE. The initial bounds are (-∞, +∞), which in code we'd represent with Integer.MIN_VALUE and Integer.MAX_VALUE. The check node.val <= min becomes Integer.MIN_VALUE <= Integer.MIN_VALUE, which is true, and we'd incorrectly reject a valid single-node tree.

The fix is to use Long.MIN_VALUE and Long.MAX_VALUE for the bounds, giving us headroom outside the int range. The node values stay as int, but the bounds we compare against are long, so the comparison never collides at the boundaries.

This is the kind of detail interviewers love to ask about. Mentioning it before they prompt for it shows attention to edge cases.

Step 4: An alternative — inorder traversal

There's a second classic approach worth knowing. An inorder traversal of a valid BST visits nodes in strictly increasing order of value. That gives us another way to validate:

1. Traverse the tree inorder.

2. Track the previous value visited.

3. At each new node, if its value is <= the previous value, the tree is invalid.

TreeNode prev = null;

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

This is elegant — it exploits a known property of BSTs without ever computing bounds explicitly. The downside is that it relies on mutable shared state (prev), which is harder to reason about and harder to parallelize. The min/max approach is purely functional: each call's behavior is determined entirely by its arguments.

Both are O(n) time and O(h) space. I'd lead with the min/max approach in an interview because the bounds make the BST invariant explicit, which is exactly what this problem is testing.

Step 5: Complexity

The recursive function visits each of the n nodes exactly once and does O(1) work per node — two comparisons and two function calls. Total time: O(n).

Space comes from the recursion stack. For a balanced tree, depth is O(log n). For a skewed tree, depth is O(n). So space is O(h) where h is the tree's height.

Both approaches — min/max bounds and inorder traversal — have the same complexity. The choice is about clarity, not performance.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Local child comparison only	O(n)	O(h)	Never — this is the bug, not a solution
Inorder traversal with monotonic check	O(n)	O(h)	Elegant alternative; mention if asked, but requires shared state
Min/max DFS validation	O(n)	O(h)	My default interview answer — explicit, robust, matches the BST definition

The min/max version is the clearest expression of the BST invariant. The inorder version is a nice second answer that demonstrates broader knowledge.

6. Pseudocode

isValidBST(root):
    return validate(root, -∞, +∞)

validate(node, min, max):
    if node is null:
        return true

    if node.val <= min or node.val >= max:
        return false

    return validate(node.left, min, node.val)
       and validate(node.right, node.val, max)

7. Edge Cases

Things to verify before claiming we're done:

• Empty tree (null root) → base case returns true. ✓

• Single-node tree → both children null; value falls within (-∞, +∞). ✓

• Duplicate values (e.g., a node with the same value as an ancestor) → strict inequality catches this. ✓

• Deeply nested violations (the rogue grandchild case) → bounds propagate from every ancestor, so the invalid descendant gets caught.

• Boundary integer values (Integer.MIN_VALUE or Integer.MAX_VALUE as node values) → bounds stored as long avoid the comparison overlap.

• Completely skewed trees (left-only or right-only chains) → still works; bounds just propagate down one side.

The boundary integer case is the one that catches candidates off-guard most often. Mentioning it explicitly during the interview is a good signal.

8. Full Code

public class ValidateBinarySearchTree {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

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

    private static boolean validate(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }

        // Each node must fall strictly within the range
        // set by all of its ancestors.
        if (node.val <= min || node.val >= max) {
            return false;
        }

        // Left subtree: upper bound tightens to the current node's value.
        // Right subtree: lower bound tightens to the current node's value.
        return validate(node.left, min, node.val)
            && validate(node.right, node.val, max);
    }
}

9. Test the Code

// Valid BST
TreeNode root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);
System.out.println(isValidBST(root));  // true

// Classic "deep violation" trap: 6 is locally fine but globally invalid
TreeNode bad = new TreeNode(5);
bad.left = new TreeNode(1);
bad.right = new TreeNode(4);
bad.right.left = new TreeNode(3);
bad.right.right = new TreeNode(6);
System.out.println(isValidBST(bad));  // false

// Empty tree
System.out.println(isValidBST(null));  // true

// Single node
System.out.println(isValidBST(new TreeNode(0)));  // true

// Boundary value: Integer.MIN_VALUE as root
TreeNode min = new TreeNode(Integer.MIN_VALUE);
System.out.println(isValidBST(min));  // true

// Duplicate values are invalid
TreeNode dup = new TreeNode(1);
dup.left = new TreeNode(1);
System.out.println(isValidBST(dup));  // false

// Deeply skewed but valid
TreeNode skewed = new TreeNode(1);
skewed.right = new TreeNode(2);
skewed.right.right = new TreeNode(3);
System.out.println(isValidBST(skewed));  // true

These hit the meaningful cases: a normal valid tree, the classic deep-violation trap, empty input, a single node, a boundary-integer case, duplicate detection, and a valid skewed tree.

10. Key Lessons

• The BST property is global, not local. A node's validity depends on every ancestor on the path from the root, not just its immediate parent. Whenever a structural rule talks about "the subtree" of a node, expect the constraint to flow downward through the recursion.

• When a problem asks you to enforce a global invariant during tree traversal, pass the relevant constraints down as parameters. Each recursive call refines the constraints based on the path taken. This pattern shows up everywhere a structure has invariants — not just BSTs.

• Recursive parameters can carry state cleanly without mutable shared variables. The min/max bounds version of this problem is purely functional, which is easier to reason about and easier to test than the inorder version's shared prev pointer.

• When a problem's input values can reach the integer boundaries, your bookkeeping variables often need wider types. long bounds instead of int is a small, cheap defense against a real bug.

• The naive solution to a problem is often almost right. The candidates who pass interviews are the ones who notice the gap between "almost right" and "actually right" before the interviewer points it out. Ask yourself: what's the simplest example that would break my current code?

The thing that makes Validate Binary Search Tree click isn't recursion or even the BST property — most candidates know both. It's the willingness to slow down at the naive solution and ask whether "left child smaller, right child bigger" really captures what the problem requires. Once you train yourself to spot the gap between local checks and global invariants, every other structural-validation problem starts to feel familiar.

Good Luck and Happy Coding!