Validate Binary Search Tree: Multiple Solutions and Complexity Analysis
A Binary Search Tree (BST) is one of the most foundational data structures in computer science. It powers everything from database indexes to in-memory ordered maps. But a tree that looks like a BST isn't necessarily a valid one — a single misplaced node can silently corrupt lookups, range queries, and deletions. In this tutorial, we'll explore what it means to validate a BST, walk through several solutions in detail, and analyze their time and space complexity.
What Is a Binary Search Tree?
A Binary Search Tree is a binary tree where every node satisfies three conditions:
- The left subtree of a node contains only nodes with keys strictly less than the node's key.
- The right subtree of a node contains only nodes with keys strictly greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
The critical insight is that the constraint is not local. A node's value must be greater than every value in its left subtree, not just its immediate left child. This is the most common source of bugs when validating BSTs.
Why Validation Matters
Validation matters because BST correctness is a precondition for the logarithmic performance guarantees of operations like search, insert, and delete. If a tree is subtly invalid — for example, a right descendant of a node is smaller than the node itself — a search may traverse the wrong path and return incorrect results. In production systems, validation is used as a sanity check after bulk inserts, deserialization, or concurrent modifications where race conditions might corrupt structure.
It's also one of the most frequently asked interview questions because it tests recursion, tree traversal, and careful boundary handling all at once.
Defining the Node
Throughout this tutorial, we'll use the following simple node definition in Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
The same structure translates directly to most languages — a value plus two optional child pointers.
Solution 1: Recursive Range Validation
The most intuitive approach is to pass down a valid range (min, max) as we recurse. At each node, we check whether its value falls within the allowed range. When we go left, we tighten the upper bound to the current node's value. When we go right, we tighten the lower bound.
def isValidBST(root: TreeNode) -> bool:
def validate(node, low, high):
# An empty tree is a valid BST
if node is None:
return True
# The current node's value must be within (low, high)
if not (low < node.val < high):
return False
# Recurse with updated bounds
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))
Complexity Analysis
Time complexity: O(n), where n is the number of nodes. We visit each node exactly once.
Space complexity: O(h) for the recursion stack, where h is the height of the tree. In the worst case (a degenerate tree), this is O(n). In a balanced tree, it's O(log n).
This is the cleanest solution and the one I'd recommend in most cases. It directly mirrors the BST definition and is easy to reason about.
Solution 2: Inorder Traversal
An inorder traversal of a valid BST produces values in strictly increasing order. We can exploit this property: traverse the tree inorder, keeping track of the previously visited value, and verify that each value is greater than the previous one.
def isValidBST(root: TreeNode) -> bool:
prev = None
def inorder(node):
nonlocal prev
if node is None:
return True
# Traverse left subtree first
if not inorder(node.left):
return False
# Check current node against previous value
if prev is not None and node.val <= prev.val:
return False
prev = node
# Traverse right subtree
return inorder(node.right)
return inorder(root)
Complexity Analysis
Time complexity: O(n) — each node is visited once.
Space complexity: O(h) for the recursion stack, identical to the range-based approach.
The inorder approach is elegant and reveals a deep property of BSTs. However, it requires careful handling of the "previous" reference, which can be tricky in languages without easy access to mutable outer state. In Python, the nonlocal keyword handles this; in Java or C++, you'd typically use an instance variable or a wrapper object.
Solution 3: Iterative Inorder Traversal
If you want to avoid recursion entirely — perhaps to dodge stack overflow on very deep trees — you can implement the inorder traversal iteratively using an explicit stack.
def isValidBST(root: TreeNode) -> bool:
stack = []
prev = None
current = root
while stack or current is not None:
# Go as far left as possible
while current is not None:
stack.append(current)
current = current.left
current = stack.pop()
# Validate ordering
if prev is not None and current.val <= prev.val:
return False
prev = current
# Move to the right subtree
current = current.right
return True
Complexity Analysis
Time complexity: O(n), since each node is pushed and popped exactly once.
Space complexity: O(h) for the explicit stack. This matches the recursive version but avoids the implicit call stack, making it safer for extremely deep trees in environments with limited stack space.
Solution 4: Collecting the Full Inorder Sequence
A simpler but less memory-efficient variant of the inorder approach is to collect all values into a list and then check whether the list is strictly increasing.
def isValidBST(root: TreeNode) -> bool:
values = []
def inorder(node):
if node is None:
return
inorder(node.left)
values.append(node.val)
inorder(node.right)
inorder(root)
# Check for strictly increasing order
for i in range(1, len(values)):
if values[i] <= values[i - 1]:
return False
return True
Complexity Analysis
Time complexity: O(n) for traversal plus O(n) for the check, which simplifies to O(n).
Space complexity: O(n) — we store every value in the list, plus O(h) for the recursion stack. This is worse than the streaming approaches, which only need O(1) extra space beyond the recursion stack.
I'd only recommend this approach when you also need the sorted sequence for another purpose, such as debugging or building a balanced tree from the values.
Common Pitfalls
Even experienced developers make mistakes on this problem. Here are the most frequent errors:
1. Only Comparing With Direct Children
The naive check — "is my left child smaller and my right child larger?" — is insufficient. Consider this tree:
10
/ \
5 15
/ \
6 20
Every node satisfies the local constraint with its immediate children, but 6 is in the right subtree of 10, violating the global BST property. The range-based and inorder approaches both catch this correctly.
2. Using Inclusive Bounds
If the BST definition allows duplicate values (some variants do), you must decide whether duplicates go left or right and adjust comparisons accordingly. The standard LeetCode definition uses strict inequalities, meaning node.val <= prev.val is invalid. Mixing up < with <= is a subtle but common bug.
3. Integer Overflow
In languages with fixed-width integers like Java or C++, using Integer.MIN_VALUE and Integer.MAX_VALUE as initial bounds fails when the tree contains those exact values. Use null sentinels or Long bounds instead:
// Java version with null sentinels
public boolean isValidBST(TreeNode root) {
return validate(root, null, null);
}
private boolean validate(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 validate(node.left, low, node.val) &&
validate(node.right, node.val, high);
}
Best Practices
- Prefer the range-based recursive solution for clarity. It maps directly to the BST definition and is the easiest to verify by inspection.
- Use the iterative inorder approach when you're concerned about stack depth, such as when validating user-supplied or deserialized trees that might be degenerate.
- Validate after deserialization. When reconstructing a BST from a serialized format, always run a validation pass before trusting the structure for lookups.
- Write property-based tests. Generate random BSTs, randomly mutate a node, and confirm your validator detects the corruption. This catches edge cases that hand-written tests miss.
- Document your duplicate policy. State explicitly whether your BST allows duplicates and, if so, where they're stored. This removes ambiguity for anyone maintaining the code.
Comparing the Solutions
Here's a quick summary to help you choose:
- Recursive range validation: Best clarity, O(n) time, O(h) space. Default choice.
- Recursive inorder (streaming): Elegant, same complexity, slightly trickier state management.
- Iterative inorder: Same complexity, avoids recursion limits. Good for hostile input.
- Full inorder list: O(n) space. Only use when you need the sorted values anyway.
Conclusion
Validating a binary search tree is a deceptively rich problem that tests your understanding of tree structure, recursion, and careful boundary handling. The range-based recursive solution is the clearest and most direct expression of the BST invariant, while the inorder traversal approaches reveal the elegant connection between BSTs and sorted sequences. Whichever solution you choose, remember that the key insight is the global nature of the BST constraint — a node must respect bounds inherited from all its ancestors, not just its immediate parent. Master this problem, and you'll have a solid foundation for tackling more advanced tree algorithms like balanced BST verification, range queries, and tree serialization.