Validate BST
Mahabharata — The Righteous Formation — Does Every Warrior Obey the BST Law?
BST नियम — हर नोड अपनी सीमा में। Min और Max — हर कदम पर सीमा सँकरी होती है॥
*BST rule — every node within its bounds. Min and max — bounds narrow with each step.*
The Story
Determine if a binary tree is a valid BST.
For `[2,1,3]`: true (1<2<3). For `[5,1,4,null,null,3,6]`: false (4 is right of 5 but 4<5 violates BST).
**The bounds approach (canonical solution):** - Each node must satisfy: `min < node.val < max` - Root: (-∞, +∞) - Go left: upper bound becomes `root.val` → (min, root.val) - Go right: lower bound becomes `root.val` → (root.val, max)
```java public boolean isValidBST(TreeNode root) { return validate(root, null, null); } boolean validate(TreeNode root, Integer min, Integer max) { if (root == null) return true; if (min != null && root.val <= min) return false; if (max != null && root.val >= max) return false; return validate(root.left, min, root.val) // Left: max = root.val && validate(root.right, root.val, max); // Right: min = root.val } ```
**Common mistake:** Only checking local parent-child relationship. Example: ``` 5 / \ 1 4 / \ 3 6 ``` Node 3: local check passes (3<4), but 3<5 violates BST (3 is in right subtree of 5, must be >5). The bounds approach catches this: when traversing right to 4, min=5. At 4: 4<5 → false ✓.
**Inorder alternative:** If inorder traversal is not strictly increasing → not BST. ```java TreeNode prev = null; boolean isValidBSTInorder(TreeNode root) { if (root == null) return true; if (!isValidBSTInorder(root.left)) return false; if (prev != null && root.val <= prev.val) return false; prev = root; return isValidBSTInorder(root.right); } ```
The Local Parent-Child Check
Check only adjacent parent-child. Misses cases where ancestor bound is violated. Incorrect.
// WRONG: only checks direct parent-child
// boolean isValidBST(TreeNode root) {
// if (root==null) return true;
// if (root.left!=null && root.left.val>=root.val) return false;
// if (root.right!=null && root.right.val<=root.val) return false;
// return isValidBST(root.left) && isValidBST(root.right);
// }
// Fails for: [5,4,6,null,null,3,7] — 3 is in right subtree but 3<5The (min, max) Bounds Narrowing Wisdom
public boolean isValidBST(TreeNode root) {
return validate(root, null, null);
}
boolean validate(TreeNode root, Integer min, Integer max) {
if (root == null) return true;
if (min != null && root.val <= min) return false;
if (max != null && root.val >= max) return false;
return validate(root.left, min, root.val)
&& validate(root.right, root.val, max);
}Step-by-Step Walkthrough
[2,2,null]: validate(2,null,null): ok. validate(2(left),null,2): 2>=2 → false. isValidBST=false ✅ (equal not allowed)
Deep Insight
**Why bounds propagation is needed:** A node deep in the tree must respect bounds set by ALL its ancestors, not just its parent. The (min, max) bounds carry ALL ancestor constraints.
**Integer vs Long vs null:** Use `Integer` with null for ±∞, or use `Long.MIN_VALUE` and `Long.MAX_VALUE` as bounds (being careful that node values might be Integer.MIN_VALUE or MAX_VALUE themselves).
**Strict inequality:** BST requires strictly less than / strictly greater than (no duplicates). Hence `root.val <= min` (not `< min`) triggers failure.
**Inorder alternative:** O(n) time, O(h) space but slightly more complex with the `prev` pointer.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(h) | Local check — INCORRECT |
| Optimal | O(n) | O(h) | Bounds narrowing DFS; each node visited once |
Pattern Recognition
✅ Validate BST: pass (min, max) bounds down the tree ✅ Left: max becomes root.val; Right: min becomes root.val ✅ Common mistake: only check local parent-child ✅ Alternative: inorder strictly increasing check **LeetCode Trigger Phrases:** → "validate binary search tree" → BST property verification → Bounds propagation in tree recursion
Bhagavad Gita 1.1
धर्मक्षेत्रे कुरुक्षेत्रे समवेता युयुत्सवः। मामकाः पाण्डवाश्चैव किमकुर्वत सञ्जय॥
In the field of righteousness, in Kurukshetra, assembled together desiring to fight — what did my sons and the sons of Pandu do, O Sanjaya?
Connection: The question opening the Gita is about order and dharma: who stands where, following what rules? Validate BST asks the same question of a tree: does every warrior (node) stand in its rightful place, obeying the BST dharma? The (min, max) bounds represent the constraints of dharma passed from each parent to its children — tightening with each level, ensuring every node respects not just its immediate parent but all its ancestors.