Validate Binary Search Tree medium
Description
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST satisfies the following recursively:
- The left subtree of a node contains only nodes with keys strictly less than the node’s value.
- The right subtree of a node contains only nodes with keys strictly greater than the node’s value.
- Both subtrees are themselves valid BSTs.
Examples
> Case 1:
Input: 2
/ \
1 3
Output: true
> Case 2:
Input: 5
/ \
1 4
/ \
3 6
Output: false # 3 is in 5's right subtree, but 3 < 5Constraints
1 <= number of nodes <= 10^4-2^31 <= node.val <= 2^31 - 1
The classic bug — and why it’s wrong
The naïve attempt: at every node, check node.left.val < node.val < node.right.val and recurse. This is wrong. It only checks the immediate children, not the whole subtree.
Counter-example:
5
/ \
1 6
/ \
3 7 ← '3' is in 5's right subtree but 3 < 5
Local check passes (6 < 7), global property fails.We need to enforce that every node in the right subtree is greater than the parent — not just the immediate child.
Approach 1: Bounds (the canonical solution)
As we recurse, pass down a valid range [lo, hi] that the current node’s value must fall within. The root accepts any value, so start with (-∞, +∞). When we go left, the upper bound tightens to the parent’s value; when we go right, the lower bound tightens.
The long types in C++/Java are not paranoid. The input value can be Integer.MIN_VALUE or Integer.MAX_VALUE. If we initialize bounds with Integer.MIN_VALUE / Integer.MAX_VALUE, the check node.val > lo rejects a legitimate root of value Integer.MIN_VALUE. Use Long (or Optional<Integer>) to safely represent “no bound yet.”
Approach 2: Inorder traversal
Recall from the Traversals page: the inorder traversal of a BST produces values in sorted order. So we just walk the tree inorder and check that each value is strictly greater than the previous one.
Why early-return on inorder failure? As soon as we find a non-increasing pair, the answer is false — there’s no point continuing. Returning early from inside an inorder walk is the standard idiom for “check a global property of the traversal.”
Iterative inorder (no recursion)
For deep trees that might blow the call stack:
def is_valid_bst(root):
stack = []
cur = root
prev = float('-inf')
while cur or stack:
while cur:
stack.append(cur); cur = cur.left
cur = stack.pop()
if cur.val <= prev: return False
prev = cur.val
cur = cur.right
return TrueThis is the iterative inorder template (see the Traversals page) with a prev value carried alongside.
Comparison
| Approach | Time | Space | Notes |
|---|---|---|---|
| Bounds recursion | O(n) | O(h) | Cleanest; no global state. |
| Inorder recursion | O(n) | O(h) | Uses BST-specific insight. |
| Iterative inorder | O(n) | O(h) | Best when recursion is risky. |
All three are O(n) and idiomatic. Pick the one that reads best in your head.
Analysis
- Time: O(n) — every node visited once.
- Space: O(h) for recursion stack or iterative stack.