Validate BST LeetCode Solution: Two Approaches to Problem #98

If you only solve one binary search tree problem before your interview, make it Validate BST (#98). This problem appears more frequently than any other BST question across Microsoft, Amazon, Google, and Bloomberg. It tests whether you truly understand what makes a binary search tree valid — and the answer is more subtle than most candidates expect.

The validate BST LeetCode problem asks a simple question: given the root of a binary tree, determine if it is a valid binary search tree. A valid BST requires that every node in the left subtree is strictly less than the current node, and every node in the right subtree is strictly greater. That definition sounds straightforward, but the word "every" is where most candidates go wrong.

In this walkthrough, you will learn two clean approaches to this problem — range checking and inorder traversal — along with edge cases that trip up even experienced engineers. Both run in O(n) time, but they reveal different insights about BST structure that carry over to dozens of related problems.

The BST property is global, not local. This is the single most important insight for this problem and for BST problems in general. Every node must satisfy constraints imposed by all of its ancestors, not just its immediate parent. When interviewers ask you to validate a binary search tree, they are testing whether you grasp this distinction.

Consider a concrete example. A root node with value 5 has a left child 1 and a right child 7. So far, this is valid. But now suppose 7 has a left child with value 4. Looking only at the local relationship, 4 is less than 7, so it belongs on the left — but 4 is also less than 5, the root. That means 4 is in the right subtree of 5 while being smaller than 5, which violates the BST property.

The formal definition is: for any node with value V, every node in its left subtree must have a value strictly less than V, and every node in its right subtree must have a value strictly greater than V. Duplicates are not allowed in a standard BST for this problem. This global constraint is what makes the naive approach fail and the correct approaches elegant.

The most common mistake on this problem is writing a recursive function that only checks whether node.left.val < node.val and node.right.val > node.val. This local check passes for many test cases but fails on trees where a deeper node violates an ancestor constraint. Interviewers specifically design test cases to catch this mistake.

Here is why the local approach fails. Suppose you have the tree [5, 1, 7, null, null, 4, 8]. The local check at node 7 sees left child 4 < 7 and right child 8 > 7, so it returns true. The local check at root 5 sees left child 1 < 5 and right child 7 > 5, so it also returns true. But the tree is invalid because 4 sits in the right subtree of 5 while being less than 5.

If you catch yourself writing a solution that only looks one level down, stop and rethink. The correct solution must propagate constraints from ancestors to descendants. Both approaches we cover next handle this correctly — one by passing explicit bounds, the other by leveraging the sorted-order property of BST inorder traversal.

The range checking approach passes an allowed range (min, max) down the recursion. At the root, the valid range is (-infinity, +infinity). When you go left, the max bound tightens to the current node value. When you go right, the min bound tightens to the current node value. If any node falls outside its allowed range, the tree is invalid.

The algorithm works as follows. Define a helper function isValid(node, min, max). If the node is null, return true — an empty tree is a valid BST. If node.val is less than or equal to min, or greater than or equal to max, return false. Otherwise, recursively check the left subtree with isValid(node.left, min, node.val) and the right subtree with isValid(node.right, node.val, max). Return true only if both recursive calls return true.

This approach has O(n) time complexity because you visit every node exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack. In the worst case of a skewed tree, h equals n, giving O(n) space. For a balanced tree, h is log(n). The range checking method is the most intuitive validate BST recursive approach and is easy to explain in an interview.

The inorder traversal of a valid BST produces values in strictly ascending order. This is a fundamental property: if you visit left, then current, then right, the values must be sorted. If at any point the current value is less than or equal to the previous value, the tree is not a valid BST.

To implement this, perform a standard inorder traversal while tracking the previously visited value. Initialize prev to negative infinity. At each node, first recurse left. Then check if the current node value is greater than prev — if not, return false. Update prev to the current value and recurse right. This BST validation inorder approach is elegant because it reduces the problem to a single comparison at each node.

The complexity is identical to range checking: O(n) time and O(h) space. You can also implement this iteratively using an explicit stack, which some interviewers prefer because it avoids potential stack overflow on extremely deep trees. The iterative version pushes all left children onto the stack, then pops and checks each node before moving to its right child.

Many candidates find the inorder approach easier to code correctly under pressure. There is no need to manage min and max parameters — you simply walk the tree in order and verify the output is sorted. This same pattern applies to Kth Smallest Element in a BST (#230) and Binary Search Tree Iterator (#173), making it a versatile technique to master.

Edge cases on validate BST are where interviews are won or lost. The first edge case is the empty tree — a null root should return true, because an empty tree is technically a valid BST. The second is a single-node tree, which is always valid regardless of the node value.

Duplicate values require attention. In LeetCode 98, the BST definition requires strict inequality — left subtree values must be strictly less than the node, and right subtree values must be strictly greater. A tree where the left child equals the parent is invalid. Make sure your comparisons use strict less-than and greater-than, not less-than-or-equal.

Integer boundary values are a classic trap. If the tree contains Integer.MIN_VALUE or Integer.MAX_VALUE, initializing your bounds to those values will cause incorrect results. In Python this is less of an issue because integers have arbitrary precision, but in Java or C++ you should use Long.MIN_VALUE and Long.MAX_VALUE, or use null to represent unbounded ranges. In JavaScript, -Infinity and Infinity work correctly for this purpose.

Validate BST is not just another tree problem — it teaches a fundamental principle that applies across the entire BST problem family. The BST property is global, meaning every node is constrained by all ancestors above it. Once you internalize this, problems like Kth Smallest Element in a BST (#230), BST Iterator (#173), and Convert Sorted Array to BST (#108) become much more approachable.

The inorder traversal insight — that a valid BST inorder walk produces sorted output — is equally powerful. This single fact lets you solve validation, search, and construction problems with the same underlying technique. When you see a BST problem in an interview, your first instinct should be to ask: can inorder traversal simplify this?

If you want to drill these BST patterns until they are automatic, YeetCode flashcards cover Validate BST and the full tree category with spaced repetition. Recognizing the pattern instantly — global constraints, inorder equals sorted — is what separates candidates who solve BST problems in five minutes from those who struggle for thirty.