Given a binary tree, decide whether it is a valid binary search tree.

The invariant is about subtrees, not about neighbours

A binary search tree requires that every key in a node's left subtree is smaller than that node and every key in its right subtree is larger. The word doing the work is "every". A node three levels down in the left subtree is still constrained by the root, and that constraint is not visible from anywhere near it.

This is why the natural-looking check fails. Comparing each node against node.left.val and node.right.val verifies a local property that a valid BST happens to satisfy, and satisfying it is not sufficient. The smallest counterexample has three nodes:

    5
   /
  1
   \
    6

Node 5 is greater than its left child 1, and node 1 is less than its right child 6, so every parent-child comparison passes. The tree is still invalid, because 6 sits in the left subtree of 5 and searching for 6 from the root would descend left and never find it. Producing this example unprompted is a good part of what the question is for, because it demonstrates you derived the check from the search property rather than from a picture of a sorted tree.

Carrying the bounds down

Turn the invariant into a parameter. Each recursive call receives the open interval the subtree is allowed to occupy: descending left replaces the upper bound with the current node's key, descending right replaces the lower bound. A node outside its interval fails immediately.

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

// low and high are EXCLUSIVE bounds; null means unbounded on that side.
private boolean within(TreeNode node, Integer low, Integer high) {
    if (node == null) return true;                 // an empty subtree satisfies any interval
    if (low != null && node.val <= low) return false;
    if (high != null && node.val >= high) return false;

    return within(node.left, low, node.val)        // left inherits low, tightens high
        && within(node.right, node.val, high);     // right tightens low, inherits high
}

Both bounds are exclusive because keys are unique by default, so a value equal to an ancestor is a violation regardless of which side it appears on. Run the counterexample through it: node 1 is checked against the interval (-inf, 5) and passes, then its right child 6 is checked against (1, 5) and fails, because descending left from 5 tightened the upper bound and descending right from 1 could only tighten the lower one. That is the mechanism the local check has no way to express.

Time is O(n), because each node is visited once and does constant work. Space is O(h) for the call stack, which is O(log n) on a balanced tree and O(n) on a degenerate chain — worth stating, because a linked-list-shaped tree of a million nodes will overflow a default thread stack and the iterative form below is the fix.

Why the bounds are boxed

Seeding the recursion with Integer.MIN_VALUE and Integer.MAX_VALUE is the version most candidates write, and it is wrong for a reason that no small test case reveals. A single-node tree holding Integer.MIN_VALUE is a perfectly valid BST, but the check node.val <= low compares that value against itself and rejects the tree. The same failure happens at any depth once a key equals a sentinel.

There are three defensible fixes and it is worth naming which one you took. Nullable bounds, as above, say "unbounded" honestly. Widening the comparison to long and seeding with values outside the int range works, and is the shortest edit. Or you can pass the ancestor nodes themselves rather than their values, since a null ancestor reference means the same thing as a null bound. What is not defensible is the sentinel version presented as if the value domain were guaranteed to exclude its own extremes; if you genuinely know the constraints forbid those keys, say so out loud, because then it is an assumption rather than a bug.

The in-order formulation

The bounds recursion is not a separate trick from the traversal argument; both come from the same definition. An in-order traversal of a BST visits keys in ascending order, and that is exactly equivalent to the subtree invariant. So a validation can simply walk in-order and check that each key is strictly greater than the previous one, keeping a single prev reference rather than a pair of bounds.

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root, prev = null;

    while (node != null || !stack.isEmpty()) {
        while (node != null) {                     // descend to the leftmost unvisited node
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (prev != null && node.val <= prev.val) return false;   // strictly increasing, so equality fails too
        prev = node;
        node = node.right;
    }
    return true;
}

This version has the same O(n) time and O(h) space, but the space is an explicit stack rather than call frames, so it cannot overflow and it can bail out the moment the ordering breaks. Materialising the whole traversal into a list first and then checking it is sorted also works and is the version to avoid volunteering, because it spends O(n) memory to answer a question that streams.

Neither approach reaches genuine O(1) extra space without mutating the tree. Morris traversal does, by temporarily threading right pointers to their in-order successors and restoring them afterwards, and it is the correct answer if an interviewer insists on constant space. Mentioning it as available and noting that it writes to the tree is better than attempting it under time pressure.

Agree the duplicate rule before you pick an operator

The definition above forbids equal keys entirely, which is the usual interview convention, but real implementations differ: some place duplicates in the right subtree, some keep a count on the node, some forbid them at the API. Each choice changes exactly one thing in your code — whether the comparison on one side is strict — and choosing silently is what causes a solution to be marked wrong for a reason the candidate did not realise was in play. Ask, state the convention, and make the operators match it.

Validation is the search property restated as a precondition: a node is legal only if the interval its ancestors left open still contains it. Anything checked only against a node's immediate children is checking a consequence, not the definition.