Introduction to Validate Binary Search Tree
The "Validate Binary Search Tree" problem is one of the most classic algorithmic challenges you'll encounter in coding interviews and competitive programming. Given the root of a binary tree, your task is to determine whether it is a valid Binary Search Tree (BST). A valid BST must satisfy a strict ordering property: every node's value must be greater than all values in its left subtree and less than all values in its right subtree.
This tutorial walks you through the problem from first principles, explores multiple solution strategies, and highlights best practices so you can confidently implement and optimize the solution in Python.
What Is a Binary Search Tree?
A Binary Search Tree is a node-based data structure where each node has at most two children, referred to as the left and right child. The defining property of a BST is that for every node:
- All values in the left subtree are strictly less than the node's value.
- All values in the right subtree are strictly greater than the node's value.
- Both subtrees must themselves be valid BSTs.
This ordering property enables efficient search, insertion, and deletion operations, typically running in O(log n) time for balanced trees.
Why Validating a BST Matters
Validating a BST is more than an academic exercise. Many real-world systems rely on BSTs (or their self-balancing variants like AVL and Red-Black trees) to maintain sorted data. If the BST property is violated, operations like search and range queries return incorrect results, potentially corrupting application logic.
Common scenarios where validation is essential include:
- Verifying tree integrity after a series of insertions and deletions.
- Debugging custom tree implementations.
- Ensuring correctness of serialization and deserialization routines.
- Interview assessments where tree manipulation is a core competency.
Understanding the Problem
Let's define the problem more formally. Given a binary tree node defined as follows:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
You must implement a function isValidBST(root) that returns True if the tree rooted at root is a valid BST, and False otherwise.
A common mistake is to only check that the immediate left child is smaller and the immediate right child is larger. This is insufficient because a violation can occur deeper in the tree. For example, a node might have a right child that is larger, but that right child's left subtree might contain a value smaller than the original node.
Solution 1: Recursive Approach with Valid Range
The most intuitive approach is to recursively traverse the tree while passing down a valid range (minimum and maximum bounds) for each node. Initially, the root can hold any value, so the bounds are negative and positive infinity. As we move left, the upper bound becomes the parent's value. As we move right, the lower bound becomes the parent's value.
Implementation
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isValidBST(root: TreeNode) -> bool:
def validate(node, low=float('-inf'), high=float('inf')):
# An empty tree is a valid BST
if not node:
return True
# The current node's value must be within the valid range
if node.val <= low or node.val >= high:
return False
# Recursively validate the left and right subtrees
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root)
How It Works
Each recursive call narrows the acceptable range for the subtree. When we traverse left, the maximum allowed value becomes the current node's value. When we traverse right, the minimum allowed value becomes the current node's value. If any node falls outside its allowed range, the function returns False immediately.
The time complexity is O(n), where n is the number of nodes, because we visit each 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 (a skewed tree), this becomes O(n).
Solution 2: Inorder Traversal Approach
An important property of a valid BST is that an inorder traversal (left, root, right) produces a strictly increasing sequence of values. We can leverage this property to validate the tree by performing an inorder traversal and checking that each value is greater than the previous one.
Implementation
def isValidBST_inorder(root: TreeNode) -> bool:
prev = None
stack = []
current = root
while stack or current:
# Go as far left as possible
while current:
stack.append(current)
current = current.left
# Process the next node in inorder
current = stack.pop()
# Check the ordering constraint
if prev is not None and current.val <= prev:
return False
prev = current.val
current = current.right
return True
How It Works
This iterative inorder traversal uses an explicit stack to avoid recursion. We traverse to the leftmost node, process it, then move to the right subtree. After processing each node, we compare its value to the previously seen value. If the current value is not strictly greater, the tree is not a valid BST.
The time complexity remains O(n) and the space complexity is O(h) for the stack. This approach is often preferred because it can short-circuit early as soon as a violation is detected, and it avoids the overhead of recursive function calls.
Solution 3: Recursive Inorder Traversal
If you prefer a recursive style but still want to use the inorder property, you can implement it with a closure that tracks the previous value.
def isValidBST_recursive_inorder(root: TreeNode) -> bool:
prev = [None] # Use a list to allow mutation in nested function
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if prev[0] is not None and node.val <= prev[0]:
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
Using a list to wrap the prev variable is a common Python idiom for mutable state inside nested functions. Alternatively, you could use the nonlocal keyword introduced in Python 3.
Testing Your Solution
Thorough testing is essential. Let's build a few test cases to verify correctness.
def build_tree(values):
"""Build a binary tree from a level-order list of values."""
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# Test case 1: A valid BST
# 2
# / \
# 1 3
tree1 = build_tree([2, 1, 3])
print(isValidBST(tree1)) # Expected: True
# Test case 2: An invalid BST
# 5
# / \
# 1 4
# / \
# 3 6
tree2 = build_tree([5, 1, 4, None, None, 3, 6])
print(isValidBST(tree2)) # Expected: False
# Test case 3: Single node
tree3 = build_tree([1])
print(isValidBST(tree3)) # Expected: True
# Test case 4: Empty tree
tree4 = build_tree([])
print(isValidBST(tree4)) # Expected: True
# Test case 5: Violation in deep subtree
# 10
# / \
# 5 15
# / \
# 6 20
tree5 = build_tree([10, 5, 15, None, None, 6, 20])
print(isValidBST(tree5)) # Expected: False (6 is less than 10)
Best Practices
Handle Edge Cases Explicitly
Always consider edge cases such as an empty tree, a single-node tree, trees with duplicate values, and highly skewed trees. An empty tree and a single-node tree are both valid BSTs by definition. Duplicate values violate the strict ordering property, so your validation should return False for them.
Use Strict Inequality
Remember that BST validation requires strict inequality. A node's value must be strictly less than or strictly greater than the bounds. Using <= and >= in comparisons ensures duplicates are correctly rejected.
Choose the Right Approach
The range-based recursive approach is often the easiest to explain and reason about during interviews. The inorder traversal approach is elegant and leverages a fundamental BST property. Choose the approach that best fits your context and the constraints of your problem.
Avoid Common Pitfalls
- Do not only compare a node with its immediate children. Always validate against the entire valid range inherited from ancestors.
- Be cautious with integer overflow in languages with fixed-width integers. Python handles arbitrary precision integers natively, so this is less of a concern.
- When using
float('-inf')andfloat('inf'), be aware that comparing integers with floats works correctly in Python, but mixing types can be surprising in other languages.
Optimize for Early Termination
Both the range-based and inorder approaches can short-circuit as soon as a violation is found. Ensure your implementation returns immediately upon detecting an invalid node rather than continuing to traverse the entire tree unnecessarily.
Conclusion
Validating a Binary Search Tree is a foundational problem that reinforces your understanding of tree traversal, recursion, and the BST ordering property. Whether you choose the range-based recursive approach or the inorder traversal method, the key insight is that every node must satisfy constraints inherited from all of its ancestors, not just its immediate parent. By mastering both implementations, understanding their time and space complexities, and rigorously testing edge cases, you'll be well-equipped to tackle this problem and related tree challenges in interviews and real-world applications alike.