Validate Binary Search Tree
Problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST) where for every node, all nodes in its left subtree are strictly less than the node's value, and all nodes in its right subtree are strictly greater.
- The number of nodes in the tree is in the range [1, 10⁴]
- −2³¹ ≤ Node.val ≤ 2³¹ - 1
Example
root = [2,1,3]trueStarting at the root node with value 2, the algorithm recursively checks the left subtree with an updated upper boundary of 2 and the right subtree with a lower boundary of 2. The left child node 1 is within the valid range (-inf, 2), and the right child node 3 is within (2, inf). Both subtrees are valid BSTs, so the entire tree is valid.
Approach
Straightforward Solution
A naive approach might check only the immediate left and right children for ordering, which fails for deeper violations. This approach is insufficient because it ignores the global ordering constraints imposed by ancestor nodes.
Core Observation
A BST is defined by the strict ordering of node values relative to all nodes in their subtrees, not just their immediate children. This means each node must lie within a valid value range defined by its ancestors.
Path to Optimal
The key insight is to carry down boundary constraints during a depth-first traversal. Each recursive call receives a valid range (left_boundary, right_boundary) that the current node's value must satisfy. For the left subtree, the right boundary becomes the current node's value; for the right subtree, the left boundary becomes the current node's value. This ensures all nodes respect the BST property globally, not just locally.
Optimal Approach
Implement a recursive DFS helper that takes a node and its valid value boundaries. If the node is null, return true. If the node's value violates the boundaries, return false. Recursively validate the left subtree with updated upper bound and the right subtree with updated lower bound. The initial call uses (-inf, +inf) as boundaries. This approach guarantees O(n) time by visiting each node once and O(h) space for recursion stack, where h is the tree height.
Time
O(n)
Each node is visited exactly once in the DFS traversal, and boundary checks are O(1) operations per node.
Space
O(h)
The recursion stack depth corresponds to the height of the tree, which is O(h). No additional data structures proportional to n are used.
Pattern Spotlight
DFS (Boundary-Constrained Validation)
When validating global ordering constraints in a tree, propagate value boundaries down the recursion to enforce strict inequalities at every node, ensuring local checks respect global BST properties.
Solution
| 1 | class Solution:
|
| 2 | def isValidBST(self, root: TreeNode) -> bool:
|
| 3 |
|
| 4 | def is_valid(node, left_boundary, right_boundary):
|
| 5 | if not node:
|
| 6 | return True
|
| 7 |
|
| 8 | if not (left_boundary < node.val < right_boundary):
|
| 9 | return False
|
| 10 |
|
| 11 | return (is_valid(node.left, left_boundary, node.val) and
|
| 12 | is_valid(node.right, node.val, right_boundary))
|
| 13 |
|
| 14 | return is_valid(root, float("-inf"), float("inf")) |
| 1 | import java.lang.Long; |
| 2 | |
| 3 | class Solution { |
| 4 | public boolean isValidBST(TreeNode root) { |
| 5 | return isValid(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY); |
| 6 | } |
| 7 | |
| 8 | private boolean isValid(TreeNode node, double leftBoundary, double rightBoundary) { |
| 9 | if (node == null) { |
| 10 | return true; |
| 11 | } |
| 12 | |
| 13 | if (!(leftBoundary < node.val && node.val < rightBoundary)) { |
| 14 | return false; |
| 15 | } |
| 16 | |
| 17 | return isValid(node.left, leftBoundary, node.val) && |
| 18 | isValid(node.right, node.val, rightBoundary); |
| 19 | } |
| 20 | } |
| 1 | #include <limits> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | bool isValidBST(TreeNode* root) { |
| 8 | return isValid(root, -numeric_limits<double>::infinity(), numeric_limits<double>::infinity()); |
| 9 | } |
| 10 | |
| 11 | private: |
| 12 | bool isValid(TreeNode* node, double leftBoundary, double rightBoundary) { |
| 13 | if (node == nullptr) { |
| 14 | return true; |
| 15 | } |
| 16 | |
| 17 | if (!(leftBoundary < node->val && node->val < rightBoundary)) { |
| 18 | return false; |
| 19 | } |
| 20 | |
| 21 | return isValid(node->left, leftBoundary, node->val) && |
| 22 | isValid(node->right, node->val, rightBoundary); |
| 23 | } |
| 24 | }; |
| 1 | var isValidBST = function(root) { |
| 2 | function isValid(node, leftBoundary, rightBoundary) { |
| 3 | if (node === null) { |
| 4 | return true; |
| 5 | } |
| 6 | |
| 7 | if (!(leftBoundary < node.val && node.val < rightBoundary)) { |
| 8 | return false; |
| 9 | } |
| 10 | |
| 11 | return isValid(node.left, leftBoundary, node.val) && |
| 12 | isValid(node.right, node.val, rightBoundary); |
| 13 | } |
| 14 | |
| 15 | return isValid(root, -Infinity, Infinity); |
| 16 | }; |
Step-by-Step Solution
Define Helper That Validates a Node Within Boundaries
| 4 | def is_valid(node, left_boundary, right_boundary):
|
Objective
To define a recursive helper that checks whether every node stays within the valid value range imposed by its ancestors.
Key Insight
The solution is not just DFS over nodes; it is DFS with propagated constraints. The helper definition makes that contract explicit by taking a node plus a left and right boundary, which is what allows the algorithm to enforce the global BST property rather than only local parent-child ordering.
Interview Quick-Check
Core Logic
Use a helper that receives a node and its valid lower and upper boundaries.
State & Boundaries
The helper contract must be applied consistently to every subtree to enforce global ordering.
Common Pitfalls & Bugs
If the helper only compares a node with its immediate children, deeper BST violations will be missed.
Return True for Null Nodes as Base Case
| 5 | if not node:
|
| 6 | return True
|
Objective
To establish the base case of recursion where a null node is considered valid.
Key Insight
A null node represents an empty subtree, which by definition cannot violate BST properties. Returning true here allows the recursion to terminate correctly and propagate validity upwards.
Interview Quick-Check
Core Logic
Recognizing null nodes as valid subtrees is essential to correctly terminate recursion and avoid false negatives.
State & Boundaries
Base case ensures recursion stops at leaf nodes without further unnecessary checks.
Enforce Node Value Within Boundaries to Validate BST Property
| 8 | if not (left_boundary < node.val < right_boundary):
|
| 9 | return False
|
Objective
To verify that the current node's value lies strictly between the left and right boundaries.
Key Insight
This check enforces the global BST ordering constraints at each node. If the node's value violates these boundaries, the entire tree cannot be a valid BST. This is the critical correctness condition that prevents local-only checks from passing invalid trees.
Interview Quick-Check
Core Logic
The strict inequality check ensures no duplicates or out-of-range values violate BST rules.
Common Pitfalls & Bugs
Using non-strict inequalities or failing to update boundaries correctly can lead to incorrect validation.
Recursively Validate Left and Right Subtrees with Updated Boundaries
| 11 | return (is_valid(node.left, left_boundary, node.val) and
|
| 12 | is_valid(node.right, node.val, right_boundary))
|
Objective
To recursively check left and right subtrees, updating boundaries to maintain global BST constraints.
Key Insight
By passing the current node's value as the new boundary for its children, the algorithm ensures that all descendants respect the BST ordering relative to their ancestors. The left subtree's upper bound is the current node's value, and the right subtree's lower bound is the current node's value. This propagation of constraints is the core mechanism that guarantees correctness.
Interview Quick-Check
Core Logic
Boundary updates during recursion enforce the strict ordering of all nodes relative to their ancestors.
State & Boundaries
Both left and right subtree validations must return true for the current subtree to be valid.
Complexity
Each recursive call processes a subtree with updated boundaries, ensuring O(n) total time.
Initiate Validation from Root with Infinite Boundaries
| 14 | return is_valid(root, float("-inf"), float("inf")) |
Objective
To start the recursive validation from the root node with the widest possible value range.
Key Insight
Using negative and positive infinity as initial boundaries means the root node has no constraints, allowing any integer value. This sets the stage for the recursive boundary narrowing that follows, ensuring the entire tree is checked under correct global constraints.
Interview Quick-Check
Core Logic
Starting with infinite boundaries allows the recursion to impose constraints progressively as it traverses down the tree.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if not (left_boundary < node.val < right_boundary):Check if node's value violates the BST boundaries.
This strict inequality check enforces the global BST property that all node values must lie strictly between their allowed boundaries, preventing invalid trees from passing.
return FalseReturn false if node's value is out of bounds.
Immediate termination upon violation ensures no further unnecessary recursion and guarantees correctness.
return (is_valid(node.left, left_boundary, node.val) andRecursively validate the left subtree with updated upper boundary.
Passing the current node's value as the right boundary for the left subtree ensures all left descendants are strictly less than the current node, maintaining BST ordering.
is_valid(node.right, node.val, right_boundary))Recursively validate the right subtree with updated lower boundary.
Passing the current node's value as the left boundary for the right subtree ensures all right descendants are strictly greater than the current node, maintaining BST ordering.
def is_valid(node, left_boundary, right_boundary):Define the recursive helper that validates a subtree within value boundaries.
Defining a helper that carries lower and upper bounds is what turns this into a correct global BST validation rather than a local child-only check.
if not node:Check if the current node is null.
Null nodes represent empty subtrees, which are valid by definition, so returning true here correctly terminates recursion.
return TrueReturn true for null nodes.
This base case prevents further recursion and signals that no BST violation was found in this path.
return is_valid(root, float("-inf"), float("inf"))Start the validation from the root with infinite boundaries.
Using negative and positive infinity as initial boundaries allows the root node to have any value, setting the stage for recursive boundary narrowing.
Test Your Understanding
Why must the algorithm pass down updated boundary constraints rather than just comparing a node's value to its immediate children?
Because BST validity depends on the entire path from the root, not just immediate children. Passing down boundaries ensures each node respects the global ordering constraints imposed by all its ancestors, preventing violations that local checks would miss.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Validate Binary Search Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Validate Binary Search Tree drill