Validate Binary Search Tree
Validate Binary Search Tree is a medium trees & bst problem solved with the postorder + multiple return values pattern.
The best approach, range check (dfs with bounds), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from inorder must be strictly increasing up.
Problem
Decide whether a binary tree is a valid binary search tree: every node’s left subtree contains only smaller values, its right subtree only larger values, and both subtrees are BSTs themselves.
Examples
Example 1
- Input
root = [2, 1, 3]- Output
true
Example 2
- Input
root = [5, 1, 7, null, null, 4, 8]- Output
false- Why
- 4 is in 5's right subtree but smaller than 5, even though it is fine next to its parent 7.
Constraints
- The tree has
1to10^4nodes. -2^31 <= Node.val <= 2^31 - 1; duplicates make it invalid.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Inorder must be strictly increasing | O(n) | O(h) |
| Range check (DFS with bounds) | O(n) | O(h) |
1Inorder must be strictly increasing
O(n)O(h)An inorder traversal of a valid BST is strictly increasing. Walk inorder and compare each value with the previous one.
- Iterative inorder; if cur.val <= prev, return false.
class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> st = new ArrayDeque<>();
TreeNode cur = root;
Long prev = null;
while (cur != null || !st.isEmpty()) {
while (cur != null) { st.push(cur); cur = cur.left; }
cur = st.pop();
if (prev != null && cur.val <= prev) return false;
prev = (long) cur.val;
cur = cur.right;
}
return true;
}
}class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
st = []
cur = root
prev = None
while cur is not None or st:
while cur is not None:
st.append(cur)
cur = cur.left
cur = st.pop()
if prev is not None and cur.val <= prev:
return False
prev = cur.val
cur = cur.right
return Trueclass Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
optional<long long> prev;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) { st.push(cur); cur = cur->left; }
cur = st.top(); st.pop();
if (prev.has_value() && cur->val <= *prev) return false;
prev = (long long) cur->val;
cur = cur->right;
}
return true;
}
};function isValidBST(root) {
const st = [];
let cur = root;
let prev = null;
while (cur !== null || st.length > 0) {
while (cur !== null) { st.push(cur); cur = cur.left; }
cur = st.pop();
if (prev !== null && cur.val <= prev) return false;
prev = cur.val;
cur = cur.right;
}
return true;
}2Range check (DFS with bounds)
O(n)O(h)Every node must lie strictly between the bounds its ancestors set. Going left, the upper bound becomes the node's value; going right, the lower bound does. Use long to handle extreme int values.
- valid(node, low, high): null → true.
- If val <= low or val >= high → false.
- valid(left, low, val) && valid(right, val, high).
class Solution {
public boolean isValidBST(TreeNode root) {
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean valid(TreeNode n, long low, long high) {
if (n == null) return true;
if (n.val <= low || n.val >= high) return false;
return valid(n.left, low, n.val) && valid(n.right, n.val, high);
}
}class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.valid(root, float('-inf'), float('inf'))
def valid(self, n: Optional[TreeNode], low: float, high: float) -> bool:
if n is None:
return True
if n.val <= low or n.val >= high:
return False
return self.valid(n.left, low, n.val) and self.valid(n.right, n.val, high)class Solution {
public:
bool isValidBST(TreeNode* root) {
return valid(root, LLONG_MIN, LLONG_MAX);
}
private:
bool valid(TreeNode* n, long long low, long long high) {
if (n == nullptr) return true;
if (n->val <= low || n->val >= high) return false;
return valid(n->left, low, n->val) && valid(n->right, n->val, high);
}
};function isValidBST(root) {
return valid(root, -Infinity, Infinity);
}
function valid(n, low, high) {
if (n === null) return true;
if (n.val <= low || n.val >= high) return false;
return valid(n.left, low, n.val) && valid(n.right, n.val, high);
}Edge cases to test
- Values equal to Integer.MIN_VALUE or MAX_VALUE (use long bounds)
- A violation far below the ancestor
- Equal values
Hints
Hint 1
Checking only the parent is not enough. Pass down the range (low, high) each node must fall in.
FAQ
What is the best time complexity for Validate Binary Search Tree?
Range check (DFS with bounds) runs in O(n) time and O(h) extra space.
Which pattern does Validate Binary Search Tree use?
It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Children Sum in a Binary Tree, Largest BST.
Is there a brute force solution for Validate Binary Search Tree?
Yes. Inorder must be strictly increasing takes O(n) time and O(h) space. An inorder traversal of a valid BST is strictly increasing.
Which edge cases should I test for Validate Binary Search Tree?
Values equal to Integer.MINVALUE or MAXVALUE (use long bounds); A violation far below the ancestor; Equal values.