Validate Binary Search Tree: why checking only the parent is wrong

The definition of a BST sounds simple: left child less than parent, right child greater than parent. Write a solution that checks only that and you will get Wrong Answer on the second example. The definition is global, not local. Every node in the left subtree must be strictly less than the ancestor that splits them, even if that ancestor is several levels up. That distinction is what makes this problem worth studying.

[5,1,4,null,null,3,6] fails the BST property at node 4 — it is in the right subtree of 5, so it must be greater than 5. It is not. A check that only compares 4 > 1 (left child of 4's parent) would pass incorrectly. The root's value propagates as a lower bound to everything on its right.

What the constraints force

n up to 10,000 is not a pressure point. O(n) visits to every node once is the natural target and is exactly what both approaches deliver. The constraint that actually matters is the value range: -2^31 <= Node.val <= 2^31 - 1. Node values span the full 32-bit signed integer space, which means you cannot use int.MinValue and int.MaxValue as initial bounds in C# — a node at the boundary would compare equal to the sentinel, not less than or greater than it, and you would incorrectly return false for a valid tree containing Integer.MIN_VALUE.

In Python this does not bite you because float('-inf') and float('inf') are always outside the integer range. In C#, use long.MinValue and long.MaxValue as the initial bounds. The function signature changes to Validate(TreeNode node, long minVal, long maxVal) — a detail that trips up a lot of people under interview pressure.

The other thing the constraints tell you: no duplicate values are implied to be invalid. The problem statement says "strictly less than" and "strictly greater than", so equal values in left or right subtrees both fail the check. The validation condition is node.val <= minVal || node.val >= maxVal, not < or >.

Approach 1: Inorder traversal — exploiting the sorted-sequence property

A BST traversed in inorder (left -> node -> right) produces values in strictly ascending order. That observation lets you validate the tree without tracking bounds: visit every node in inorder, check that each value is strictly greater than the previous.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        return self._inorder(root)
 
    def _inorder(self, node: TreeNode) -> bool:
        if not node:
            return True
        if not self._inorder(node.left):
            return False
        if self.prev is not None and node.val <= self.prev:
            return False
        self.prev = node.val
        return self._inorder(node.right)

public class Solution {
    private long? prev = null;
 
    public bool IsValidBST(TreeNode root) {
        prev = null;
        return Inorder(root);
    }
 
    private bool Inorder(TreeNode node) {
        if (node == null) return true;
        if (!Inorder(node.left)) return false;
        if (prev.HasValue && node.val <= prev.Value) return false;
        prev = node.val;
        return Inorder(node.right);
    }
}

The C# version uses long? for prev — same reason as before. Node values span int range, so prev must survive holding int.MinValue without confusion.

Tracing through Example 2

Input: [5,1,4,null,null,3,6], which builds the tree above.

Call _inorder(5)
  -> call _inorder(1)
       -> call _inorder(null) [left of 1]: return True
       -> prev is None, set prev = 1
       -> call _inorder(null) [right of 1]: return True
     return True
  -> prev = 1, node.val = 5, 5 > 1 OK, set prev = 5
  -> call _inorder(4)
       -> call _inorder(3) [left of 4]
            -> call _inorder(null): return True
            -> prev = 5, node.val = 3, 3 <= 5 -> return False
         return False
     return False
  return False

The violation surfaces at node 3: inorder says we should see values larger than 5 in the right subtree of 5, but 3 shows up before we have left that subtree. The prev check catches it immediately.

The global instance variable problem

The prev state lives on the instance (or as a closure variable in Python). That works fine for a single call to isValidBST, but if your test framework — or a problem variant — calls the same Solution object twice, prev carries over from the previous call. The C# version explicitly resets prev = null in IsValidBST for this reason. In Python, you could move prev into a local list (prev = [None]) and mutate prev[0], which avoids the instance variable entirely and lets closures capture it cleanly.

This is not a correctness issue in practice on LeetCode, but it is the kind of statefulness that makes this approach slightly fragile. The range validation approach avoids it completely.

Approach 2: Range validation — carrying bounds through the recursion

Instead of checking after the fact (inorder sequence), pass the valid interval forward: every node receives a lower bound and an upper bound, and must fit strictly inside them. When you recurse left, the current node value becomes the new upper bound. When you recurse right, it becomes the new lower bound.

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def validate(node, min_val, max_val):
            if not node:
                return True
            if node.val <= min_val or node.val >= max_val:
                return False
            return (validate(node.left, min_val, node.val) and
                    validate(node.right, node.val, max_val))
 
        return validate(root, float('-inf'), float('inf'))

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Validate(root, long.MinValue, long.MaxValue);
    }
 
    private bool Validate(TreeNode node, long minVal, long maxVal) {
        if (node == null) return true;
        if (node.val <= minVal || node.val >= maxVal) return false;
        return Validate(node.left, minVal, node.val) &&
               Validate(node.right, node.val, maxVal);
    }
}

No instance state. Each recursive call is self-contained. The bounds accumulate as you descend: every node inherits all constraints imposed by its ancestors, not just its direct parent.

How the bounds propagate

Let me walk through the failing example again, this time with bounds:

• Root 5: bounds are (-∞, +∞). 5 fits. Recurse left with (-∞, 5), right with (5, +∞).
• Node 1: bounds are (-∞, 5). 1 fits.
• Node 4: bounds are (5, +∞). 4 <= 5 fails. Return false immediately.

The violation is found at 4 itself, not at its children. The check is node.val <= minVal, which catches 4 <= 5. No further recursion needed.

The and-short-circuit in both Python and C# means we never visit nodes 3 or 6 — once the left subtree of 4 is irrelevant (we already know 4 fails), neither is evaluated.

Why this is the version I'd write

No shared state. The function is pure: same inputs always produce the same outputs, and there is no implicit dependency on call order. Debugging a function with no side effects is much easier than debugging one that relies on mutation of self.prev. The bounds also make the invariant visible directly in the code: node.val <= minVal failing means "this node breaks the contract set by its ancestor." That mirrors the problem definition perfectly.

The inorder approach requires you to internalize a property (BST -> sorted inorder sequence) and reason that violating sort order proves an invalid BST. That reasoning is sound, but it is a level of indirection the range approach does not need.

Both are O(n) time and O(h) space. The asymptotic complexity is identical. For everything else — clarity, statelessness, debuggability — range validation wins. This is what I ship.

Edge cases and what the code actually does with them

Empty tree (root = null): both approaches return True immediately from the base case. The problem guarantees at least one node, but handling null is still correct behavior.

Single node (no children): range validation checks the value against (-inf, +inf), which always passes, then recurses into two null children that both return true. Inorder traversal visits the single node, prev is None so no comparison happens, and it returns true. Both correct.

Node value at INT_MIN or INT_MAX: in Python, no issue — float('-inf') is always less than any integer, and float('inf') is always greater. In C#, using long.MinValue and long.MaxValue means even a node with val = Int32.MinValue satisfies node.val > long.MinValue without overflow. If you had used int.MinValue as the initial lower bound, then a root node with val = int.MinValue would fail the check node.val <= minVal and return false for a valid single-node tree. That is a concrete wrong answer on a valid input.

Duplicate values (e.g., a tree where left child equals parent): the strict inequalities < minVal -> fail, > maxVal -> fail catch this. A node equal to its ancestor's value violates the BST definition ("strictly less than", "strictly greater than"). Both approaches handle duplicates correctly: inorder check node.val <= self.prev rejects equal, range check node.val <= minVal rejects equal.

Skewed tree (degenerate chain of 10,000 nodes): recursion depth reaches O(n) = 10,000 frames. Python's default recursion limit is 1,000. On LeetCode this is usually raised, but if you hit RecursionError on the inorder approach, you can either increase the limit with sys.setrecursionlimit(20000) or rewrite iteratively. The constraint n <= 10^4 is exactly where this becomes a practical concern — it is not theoretical.

Complexity table

Both visit every node exactly once and perform O(1) work per node. Space is the call stack depth, which is O(h). On a balanced tree that is O(log n); on a degenerate tree (sorted input) it is O(n). No approach has better asymptotic complexity — the difference is in code quality, not performance.

Where this sits in the series

This is the sixth problem in the trees series, and it is the first one that asks you to validate a constraint over the full subtree rather than a single node or a path. Invert Binary Tree (226), Maximum Depth of Binary Tree (104), and Same Tree (100) all do something at a node and combine results — but none of them require information from ancestors. This problem does. The range validation approach introduces the pattern of carrying accumulated state downward through recursive calls, which shows up again in problems involving path sums with targets and subtree queries with external context.

Kth Smallest Element in a BST (230) uses the sorted inorder property even more directly: instead of checking order, you use inorder traversal to find the k-th element by visit count. The traversal structure is identical to Approach 1 here; the aggregation is different.

Lowest Common Ancestor of a BST (235) exploits the BST property in a different direction — you use the ordering to decide which subtree to descend into, cutting the problem to O(h) rather than O(n). Compare that with the general binary tree LCA, where you cannot use ordering at all.

Insert into a BST (701) and Delete Node in a BST (450) round out the core BST operations. Once you are comfortable with the BST ordering invariant from validation, insertion and deletion feel natural — they are both recursive descent using the same bounds reasoning, just with a structural modification at the end.