Validate Binary Search Tree
MedPrompt
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3]
Output: trueExample 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the definition of a Binary Search Tree into a recursive algorithm. For each node, it verifies that all nodes in its left subtree are smaller and all nodes in its right subtree are larger. It then recursively performs the same validation for the left and right children. This method is straightforward but highly inefficient.
Algorithm
- The main function
isValidBST(root)serves as the entry point. - If the
rootisnull, the tree is trivially valid, so returntrue. - The core logic is to check three conditions for the current
root:- All nodes in the left subtree must have values strictly less than
root.val. This is checked by a helper function, e.g.,isSubtreeLessThan(root.left, root.val). - All nodes in the right subtree must have values strictly greater than
root.val. This is checked by another helper, e.g.,isSubtreeGreaterThan(root.right, root.val). - Both the left and right subtrees must themselves be valid binary search trees. This is checked by recursively calling
isValidBST(root.left)andisValidBST(root.right).
- All nodes in the left subtree must have values strictly less than
- The function returns
trueonly if all three conditions are met for every node in the tree.
Walkthrough
The algorithm works by defining a function isValidBST(node) that checks if the subtree rooted at node is a valid BST. For this to be true, three properties must hold: the values in the left subtree must all be less than node.val, the values in the right subtree must all be greater than node.val, and both the left and right subtrees must also be valid BSTs. This leads to a recursive solution where for each node, we traverse its entire left and right subtrees to check the value constraints, and then make recursive calls on its children. The repeated traversals of the same nodes make this approach very slow.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public boolean isValidBST(TreeNode root) { if (root == null) { return true; } // Check if all nodes in left subtree are less than root's value // and all nodes in right subtree are greater than root's value. // Then, recursively validate the left and right subtrees. return isSubtreeLessThan(root.left, root.val) && isSubtreeGreaterThan(root.right, root.val) && isValidBST(root.left) && isValidBST(root.right); } // Helper to check if all nodes in a subtree are less than a given value. private boolean isSubtreeLessThan(TreeNode node, int value) { if (node == null) { return true; } return node.val < value && isSubtreeLessThan(node.left, value) && isSubtreeLessThan(node.right, value); } // Helper to check if all nodes in a subtree are greater than a given value. private boolean isSubtreeGreaterThan(TreeNode node, int value) { if (node == null) { return true; } return node.val > value && isSubtreeGreaterThan(node.left, value) && isSubtreeGreaterThan(node.right, value); }}Complexity
Time
O(N^2)
Space
O(N)
Trade-offs
Pros
Simple to understand and implement as it directly follows the definition of a BST.
Cons
Extremely inefficient due to redundant computations. The same subtrees are traversed multiple times.
Time complexity is poor, making it impractical for large trees.
A much more efficient approach is to perform a single top-down traversal. Instead of re-validating subtrees, we pass down the valid range of values (lower and upper bounds) that each node must fall into. The root can be any value, but as we descend, the constraints become tighter.
Algorithm
- Define a recursive helper function
validate(node, low, high). - The initial call from the main function will be
validate(root, null, null), wherenullforlowandhighrepresents negative and positive infinity, respectively. - In the
validatefunction:- If
nodeisnull, it's a valid empty subtree, returntrue. - Check if the current node's value violates the bounds. If
lowis notnullandnode.val <= low, or ifhighis notnullandnode.val >= high, returnfalse. - Recursively call
validatefor the left child, updating the upper bound to the current node's value:validate(node.left, low, node.val). - Recursively call
validatefor the right child, updating the lower bound to the current node's value:validate(node.right, node.val, high). - Return
trueonly if both recursive calls returntrue.
- If
Walkthrough
This approach avoids redundant work by keeping track of the valid value range for each node. The root node can have any value, so its range is effectively (-∞, +∞). When we move to a left child of a node p, we know its value must be less than p.val. So, the valid range for the left child becomes (parent's lower bound, p.val). Similarly, when we move to a right child, its value must be greater than p.val, so its range becomes (p.val, parent's upper bound). We traverse the tree once, and at each node, we check if its value is within the allowed range. If any node violates its range, the tree is not a valid BST.
To handle the full range of integer values, including Integer.MIN_VALUE and Integer.MAX_VALUE, we can use Integer wrapper objects for the bounds, where null represents infinity.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public boolean isValidBST(TreeNode root) { // Use null to represent negative and positive infinity. return validate(root, null, null); } private boolean validate(TreeNode node, Integer low, Integer high) { // An empty tree is a valid BST. if (node == null) { return true; } // The current node's value must be within the bounds. if ((low != null && node.val <= low) || (high != null && node.val >= high)) { return false; } // Recursively check the left and right subtrees with updated bounds. return validate(node.left, low, node.val) && validate(node.right, node.val, high); }}Complexity
Time
O(N)
Space
O(H)
Trade-offs
Pros
Optimal time complexity of O(N) as it visits each node only once.
Conceptually clean and directly enforces the global BST property at each node.
Cons
For very deep or skewed trees, the recursion depth can become very large, potentially leading to a
StackOverflowError.
This approach is based on a key property of BSTs: an in-order traversal (Left-Root-Right) visits the nodes in non-decreasing order. For a valid BST, this order must be strictly increasing. We can perform an in-order traversal and check if each node's value is strictly greater than the previously visited node's value. An iterative implementation using a stack is efficient and avoids recursion depth issues.
Algorithm
- Initialize an empty
Stackto aid the traversal and a variableprev(e.g., a nullableInteger) tonull. - Initialize a
currentpointer to theroot. - Start a loop that continues as long as
currentis notnullor thestackis not empty.- While
currentis notnull, push it onto thestackand move to its left child (current = current.left). This finds the next node in the in-order sequence. - Once
currentisnull, pop a node from thestack. This is the current node to be processed. - Check the BST property: If
previs notnulland the popped node's value is less than or equal toprev, the order is violated. Returnfalse. - Update
prevwith the current node's value. - Move to the right child of the popped node (
current = node.right) to continue the traversal.
- While
- If the loop completes without returning
false, the entire tree has been traversed in sorted order. Returntrue.
Walkthrough
Instead of passing value ranges down the tree (top-down), we can verify the BST property by checking the node order during an in-order traversal (bottom-up, in a sense). The in-order traversal visits the leftmost node first, then its parent, then the parent's right child's subtree. By keeping track of the value of the previously visited node, we can ensure that the current node's value is always greater. If we ever find a node whose value is less than or equal to the previous node's value, we have found a violation of the BST property.
The iterative approach uses an explicit stack to simulate the recursion of an in-order traversal. This makes the solution robust against stack overflow errors that can occur with deep, unbalanced trees.
import java.util.Stack; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public boolean isValidBST(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); Integer prev = null; // Use Integer wrapper to handle the first element TreeNode current = root; while (current != null || !stack.isEmpty()) { // Go to the leftmost node while (current != null) { stack.push(current); current = current.left; } // Visit the node at the top of the stack current = stack.pop(); // Check if the inorder property is violated if (prev != null && current.val <= prev) { return false; } prev = current.val; // Move to the right subtree current = current.right; } return true; }}Complexity
Time
O(N)
Space
O(H)
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(H).
The iterative approach is robust and avoids potential stack overflow errors on skewed trees.
Cons
The logic can be slightly less intuitive to grasp compared to the direct recursive validation.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private TreeNode prev ; public bool IsValidBST ( TreeNode root ) { prev = null ; return dfs ( root ); } private bool dfs ( TreeNode root ) { if ( root == null ) { return true ; } if (! dfs ( root . left )) { return false ; } if ( prev != null && prev . val >= root . val ) { return false ; } prev = root ; if (! dfs ( root . right )) { return false ; } return true ; } }/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Integer prev ; public boolean isValidBST ( TreeNode root ) { prev = null ; return dfs ( root ); } private boolean dfs ( TreeNode root ) { if ( root == null ) { return true ; } if (! dfs ( root . left )) { return false ; } if ( prev != null && prev >= root . val ) { return false ; } prev = root . val ; if (! dfs ( root . right )) { return false ; } return true ; } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function (root) { let prev = null; let dfs = function (root) { if (!root) { return true; } if (!dfs(root.left)) { return false; } if (prev && prev.val >= root.val) { return false; } prev = root; if (!dfs(root.right)) { return false; } return true; }; return dfs(root); };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * prev ; bool isValidBST ( TreeNode * root ) { prev = nullptr ; return dfs ( root ); } bool dfs ( TreeNode * root ) { if ( ! root ) return true ; if ( ! dfs ( root -> left )) return false ; if ( prev && prev -> val >= root -> val ) return false ; prev = root ; if ( ! dfs ( root -> right )) return false ; return true ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : # recursive def isValidBST ( self , root : Optional [ TreeNode ]) -> bool : def dfs ( root , mi , ma ): if not root : return True return mi < root . val < ma and dfs ( root . left , mi , root . val ) and dfs ( root . right , root . val , ma ) return dfs ( root , - math . inf , math . inf ) class Solution : # iterative def isValidBST ( self , root : TreeNode ) -> bool : # store (node, lower, upper) tuples in a single queue queue = [( root , None , None )] # another option: # queue = [(root, -math.inf, math.inf)] while queue : node , lower , upper = queue . pop ( 0 ) if node is None : continue val = node . val if lower is not None and val <= lower : return False if upper is not None and val >= upper : return False queue . append (( node . right , val , upper )) queue . append (( node . left , lower , val )) return True ############ class Solution : def isValidBST ( self , root : Optional [ TreeNode ]) -> bool : def isValidBST ( root : Optional [ TreeNode ], minNode : Optional [ TreeNode ], maxNode : Optional [ TreeNode ]) -> bool : if not root : return True if minNode and root . val <= minNode . val : return False if maxNode and root . val >= maxNode . val : return False return isValidBST ( root . left , minNode , root ) and isValidBST ( root . right , root , maxNode ) return isValidBST ( root , None , None ) ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isValidBST ( self , root : TreeNode ) -> bool : def dfs ( root ): nonlocal prev if root is None : return True if not dfs ( root . left ): return False if prev >= root . val : return False prev = root . val if not dfs ( root . right ): return False return True prev = - inf return dfs ( root ) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def isValidBST ( self , root ): """ :type root: TreeNode :rtype: bool """ prev = - float ( "inf" ) stack = [( 1 , root )] while stack : p = stack . pop () if not p [ 1 ]: continue if p [ 0 ] == 0 : if p [ 1 ]. val <= prev : return False prev = p [ 1 ]. val else : stack . append (( 1 , p [ 1 ]. right )) stack . append (( 0 , p [ 1 ])) stack . append (( 1 , p [ 1 ]. left )) return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.