Validate BST LeetCode 98 Deep Dive

LeetCode 98 — Validate Binary Search Tree — asks you to determine whether a given binary tree satisfies the BST property: for every node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater. This constraint applies to entire subtrees, not just immediate children.

The problem appears in nearly every major interview loop covering trees, because it exposes a critical conceptual trap and tests whether the candidate understands BST semantics at depth. A tree can look locally valid at every parent-child pair yet still be a globally invalid BST if a deeply nested node violates an ancestor constraint.

The constraints are deliberately permissive: the tree can have up to 10,000 nodes, and node values range from -2^31 to 2^31 - 1. The value range matters — it rules out using 0 or Integer.MIN_VALUE as sentinel bounds, and requires float("-inf") in Python or Long.MIN_VALUE/Long.MAX_VALUE in Java to safely initialize the recursive bounds.

The most common error candidates make is checking only the immediate children: verify that node.left.val < node.val and node.right.val > node.val, then recurse. This passes many test cases but fails on trees where a deeply nested node violates an ancestor constraint. The classic counterexample: a tree rooted at 5, with left child 4, and a right child of 4 with its own right child 6. Every parent-child pair looks valid, but 6 is in the left subtree of 5, so it must be less than 5 — and it is not.

This mistake is so common that LeetCode designed the problem's canonical test cases specifically to expose it. The fix is not to compare adjacent nodes — it is to propagate inherited bounds downward. Every time you recurse left, the current node's value becomes a new upper bound that the entire left subtree must respect. Every time you recurse right, the current node's value becomes a new lower bound.

Understanding this distinction — local validity versus global validity — is the key insight for this problem and for understanding BSTs in general. A BST's power comes from the global invariant: every node is bounded not just by its parent but by every ancestor on its path from the root.

The bounds approach defines a helper validate(node, minVal, maxVal) that returns true if the subtree rooted at node is a valid BST with all values strictly between minVal and maxVal. At the root, call validate(root, -infinity, +infinity). Every node must satisfy minVal < node.val < maxVal; if it does not, return false immediately.

When recursing left, the current node's value becomes the new upper bound — the entire left subtree must have values less than node.val. When recursing right, node.val becomes the new lower bound. These updated bounds propagate downward through the entire tree, ensuring that every node respects every ancestor constraint, not just its immediate parent.

This approach runs in O(n) time since each node is visited exactly once, and uses O(h) space for the recursion stack where h is the tree height — O(log n) for balanced trees and O(n) for skewed trees. In Python use float("-inf") and float("inf"). In Java use Long.MIN_VALUE and Long.MAX_VALUE to avoid integer overflow when node values sit at the 32-bit boundary.

The inorder traversal approach leverages a fundamental BST property: an inorder traversal of a valid BST always produces values in strictly increasing order. This transforms the validation problem into a sequence problem — perform an inorder traversal and verify that each value is strictly greater than the previous one. If any violation is found, the tree is not a valid BST.

Implementation uses a single pointer or instance variable to track the previously visited inorder value, initialized to negative infinity. During inorder traversal — left subtree, current node, right subtree — compare each node's value against the previous. If current.val is not strictly greater than previous, return false immediately. Otherwise update previous and continue.

The inorder approach has the same O(n) time and O(h) space as the bounds approach. Its advantage is conceptual clarity: it makes the connection between BSTs and sorted sequences explicit. Many candidates find it easier to reason about — instead of thinking about abstract bounds, you are simply checking if the traversal output is sorted. The iterative version using an explicit stack avoids recursion depth limits for very deep trees.

Morris traversal is a threading technique that performs an inorder traversal of a binary tree without using a recursion stack or an explicit stack data structure. It temporarily modifies the tree's right pointers to create threads — shortcuts back to inorder successors — and then restores them after visiting each node. The result is O(n) time and O(1) extra space.

The algorithm maintains a current pointer starting at root. For each node, if it has no left child, visit the node and move right. If it has a left child, find the inorder predecessor (rightmost node in the left subtree). If the predecessor's right pointer is null, set it to current (create a thread) and move left. If the predecessor's right points back to current, the left subtree has been processed: unthread it, visit current, and move right.

For BST validation using Morris traversal, check the BST property while visiting each node during the traversal: compare the current node's value against the previously visited value and return false if the current is not strictly greater. This gives O(n) time with O(1) extra space — optimal for memory-constrained environments where the tree could be extremely deep and the call stack is limited.

Python bounds version: def isValidBST(root): 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")). Clean single-function solution with no helper class needed.

Python inorder version using prev pointer: self.prev = float("-inf") at the class level, then def inorder(node): if not node: return True; if not inorder(node.left): return False; if node.val <= self.prev: return False; self.prev = node.val; return inorder(node.right). Java equivalent uses a long[] prev = {Long.MIN_VALUE} array to pass by reference across recursive calls, avoiding a class field.

Time complexity for all three approaches is O(n) — each node is visited exactly once. Space complexity for the recursive bounds and inorder approaches is O(h) for the call stack, where h is the tree height. Morris traversal achieves O(1) extra space at the cost of temporarily modifying the tree. For interviews, the bounds approach is the standard answer; mention Morris traversal as the space-optimal alternative if asked for optimization.

Kth Smallest Element in a BST (LeetCode 230) directly uses inorder traversal to extract the kth value from a BST in sorted order, making it a natural follow-up to Validate BST. Once you are comfortable with inorder traversal for validation, applying the same traversal for selection problems is straightforward. Lowest Common Ancestor of a BST (LeetCode 235) exploits the BST property to find the LCA without full tree traversal — if both target values are less than the current node, LCA is in the left subtree; if both greater, it is in the right subtree.

Subtree of Another Tree (LeetCode 572) and Validate BST together illustrate the two most important tree recursive patterns: structural comparison and constraint propagation. Both use the same recursive skeleton but solve fundamentally different questions. Studying them side by side cements recursive tree thinking more effectively than studying either in isolation.

For comprehensive tree preparation, the BST family — Validate BST, Kth Smallest, LCA of BST, Insert into BST (LeetCode 701), and Delete Node in BST (LeetCode 450) — forms a complete set of operations that covers every BST manipulation pattern tested in top-tier interviews. Combining these with the general binary tree problems (Max Depth, Same Tree, Binary Tree Level Order Traversal) gives full coverage of the tree section.