Validate Binary Search Tree — Solution in Python, Java & C++
Validate Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Validate Binary Search Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, decide whether it is a valid binary search tree:
- every value in a node's left subtree is strictly smaller than the node's value;
- every value in a node's right subtree is strictly larger than the node's value;
- both subtrees are themselves binary search trees.
Return true if it is, false otherwise. Equal values anywhere make the tree invalid.
Example 1
Input: root = [2,1,3]
Output: true
Explanation: 1 < 2 < 3 with 1 on the left and 3 on the right.
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root's right child 4 is smaller than the root 5.
Example 3
Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Each parent-child pair looks right, but 3 sits in the root's right subtree while being smaller than 5.
Constraints
1 <= number of nodes <= 10^4-2^31 <= Node.val <= 2^31 - 1
Hints for Validate Binary Search Tree
Hint 1
Comparing each node only with its two children is not enough — a value deep in a right subtree must still exceed the root.
Hint 2
Think about what an in-order traversal (left, node, right) of a valid binary search tree produces.
Hint 3
Walk the tree in order and check that every value is strictly greater than the one visited just before it; remember whether a previous value exists rather than starting from a sentinel, since values reach the 32-bit limits.
How to solve Validate Binary Search Tree
A binary tree is a binary search tree exactly when its in-order sequence is strictly increasing, so one in-order walk comparing each value with the previous one decides it.
Approach
- Walk the tree in order with an explicit stack: push the current node and go left until there is no left child.
- Pop a node. If a previous value exists and the node's value is not strictly greater, return false.
- Record the node's value as the previous one and continue with its right child.
- If the walk finishes, return true.
Why it works
In-order visits a node's whole left subtree, then the node, then its whole right subtree. If the tree is a binary search tree, the sequence is therefore increasing by induction on subtrees. Conversely, if the sequence is strictly increasing, every value of a left subtree comes before the node in the sequence and so is smaller, and every value of a right subtree comes after and is larger — which is the definition.
Complexity
- Time —
O(n) - Space —
O(h), h the height of the tree
Pitfalls
- Checking only
left.val < node.val < right.valaccepts[5,4,6,null,null,3,7]. - Starting
prevat the smallest 32-bit integer rejects a tree whose smallest value is exactly -2^31; use a flag or a wider type. - Duplicates are invalid: compare with
<=, not<.
Reference solution
Python
from typing import Optional
def isValidBST(root: Optional[TreeNode]) -> bool:
stack = []
node = root
prev = None
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if prev is not None and node.val <= prev:
return False
prev = node.val
node = node.right
return TrueJava
public static boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
boolean hasPrev = false;
int prev = 0;
while (!stack.isEmpty() || node != null) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
if (hasPrev && node.val <= prev) return false;
hasPrev = true;
prev = node.val;
node = node.right;
}
return true;
}C++
bool isValidBST(TreeNode* root) {
vector<TreeNode*> stack;
TreeNode* node = root;
bool hasPrev = false;
int prev = 0;
while (!stack.empty() || node) {
while (node) { stack.push_back(node); node = node->left; }
node = stack.back();
stack.pop_back();
if (hasPrev && node->val <= prev) return false;
hasPrev = true;
prev = node->val;
node = node->right;
}
return true;
}JavaScript
var isValidBST = function(root) {
var stack = [], node = root, hasPrev = false, prev = 0;
while (stack.length > 0 || node !== null) {
while (node !== null) { stack.push(node); node = node.left; }
node = stack.pop();
if (hasPrev && node.val <= prev) return false;
hasPrev = true;
prev = node.val;
node = node.right;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals