You are handed a binary tree that “should be” a search tree: left smaller, right larger. A review comment said “just check each node against its two children.” That accepts this shape:

      10
     /  \
    5    15
        /
       6

15 is greater than 10. 6 is less than 15. Every local child check passes. 6 sits in the right subtree of 10, so it is also supposed to be greater than 10. It is not. The tree is not a BST.

A BST is valid only if every key lies inside the open range implied by the path from the root. The BST post owns the invariant, the lopsided spine, and why Java does not ship java.util.BST. The binary tree post owns shape and traversals. Here we only care about carrying low and high down the walk so a grandchild cannot hide on the wrong side.

The problem

Given the root of a binary tree, return whether it is a valid binary search tree. Duplicate keys are not allowed (strict less / strict greater). An empty tree is valid.

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

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

Note: Checking node.left.val < node.val and node.right.val > node.val is necessary and not sufficient. The invariant is recursive: every key in the left subtree is less than the node, not just the left child.

Carry the allowed range

At the root the range is unbounded. When you step left, the current value becomes the new upper bound. When you step right, it becomes the new lower bound. A node is illegal when it is not strictly inside (low, high).

node 10, range (-∞, +∞)   ok, left gets (-∞, 10), right gets (10, +∞)
node 5,  range (-∞, 10)   ok, left (-∞, 5), right (5, 10)
node 15, range (10, +∞)   ok, left (10, 15), right (15, +∞)
node 6,  range (10, 15)   6 is not > 10   invalid

Use Long sentinels (or null bounds) so a node whose value is Integer.MIN_VALUE or Integer.MAX_VALUE still has room to fail a bound. Comparing against Integer.MIN_VALUE as “no lower bound” rejects a legal MIN_VALUE root.

boolean isValidBST(TreeNode root) {
    return valid(root, null, null);
}

boolean valid(TreeNode node, Integer low, Integer 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);
}

Time is O(n) — each node is checked once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack is the same bound without blowing the JVM stack.

Inorder is a second correct procedure

An inorder walk of a BST yields strictly increasing keys. Keep the previous value. If the current key is not greater, the tree is invalid.

boolean isValidBSTInorder(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    Integer prev = null;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        if (prev != null && current.val <= prev) {
            return false;
        }
        prev = current.val;
        current = current.right;
    }
    return true;
}

Same O(n) time, O(h) space. The range walk fails as soon as a node sits outside its ancestors’ bounds — you do not have to finish a left-to-right dump. Prefer bounds at the board unless they ask for inorder; it is one idea (the invariant) instead of “traversal plus a remembered previous.”

Note: Collecting every inorder value into a list, then scanning the list, is correct and wastes O(n) extra memory on a copy you do not need.

What interviewers usually poke next

  • Duplicates allowed on one side. Change <= / >= to match the policy. Name the policy before you edit the comparisons.
  • int extrema. If they insist on primitive bounds, use long low/high starting at Long.MIN_VALUE / Long.MAX_VALUE.
  • Recover the tree / find the swapped pair. Two inorder inversions. Different problem; do not start mutating in isValidBST.
  • Why not check only children? Draw the 10 / 15 / 6 counterexample. That drawing is the whole point of this question.

You are done with this problem when you can reject that counterexample without building an inorder list, and you can explain why Integer.MIN_VALUE as a sentinel is a trap.