Definition
- BST invariant – every node's value must be greater than all values in its left subtree and less than all values in its right subtree.
- Global property – the invariant applies across the entire subtree, not just the immediate children.
- Bounds approach – thread a valid open interval (low, high) down the recursion; each node must lie strictly within it.
- Tightening – going left sets the current value as the new upper bound; going right sets it as the new lower bound.
- Inorder alternative – a valid BST's inorder traversal produces strictly increasing values.
Rajesh organizes account records at the National Bank of India in a tree so searches are fast, with smaller account numbers to the left and larger to the right. To verify the tree is correctly ordered, he checks each record against an allowed range. Starting with no limits, as he goes left the numbers must all stay below the parent, and as he goes right they must all stay above it. If any record falls outside the range inherited from its ancestors, the ordering is broken.
Understanding the Concepts
What is the problem?
Given the root of a binary tree, determine whether it is a valid binary search tree (BST). A valid BST requires that every node's value is strictly greater than all values in its left subtree and strictly less than all values in its right subtree.
package com.bank.tree;
public class ValidateBST {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private static boolean validate(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return validate(node.left, low, node.val)
&& validate(node.right, node.val, high);
}
public static void main(String[] args) {
// 50000
// / \
// 30000 70000
// / \ \
// 20000 40000 80000
TreeNode root = new TreeNode(50000);
root.left = new TreeNode(30000);
root.right = new TreeNode(70000);
root.left.left = new TreeNode(20000);
root.left.right = new TreeNode(40000);
root.right.right = new TreeNode(80000);
System.out.println("Valid BST: " + isValidBST(root));
}
}
Valid BST: true
Why is checking only immediate children wrong?
The common mistake is verifying only that a node is greater than its left child and less than its right child. This misses violations where a deep node satisfies its parent but violates an ancestor's bound.
package com.bank.tree;
public class NaiveCheckFails {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { this.val = v; }
}
// WRONG: checks only immediate children
static boolean naiveCheck(TreeNode node) {
if (node == null) return true;
if (node.left != null && node.left.val >= node.val) return false;
if (node.right != null && node.right.val <= node.val) return false;
return naiveCheck(node.left) && naiveCheck(node.right);
}
public static void main(String[] args) {
// 50000
// / \
// 30000 70000
// \
// 60000 <-- violates 50000's left subtree constraint!
TreeNode root = new TreeNode(50000);
root.left = new TreeNode(30000);
root.right = new TreeNode(70000);
root.left.right = new TreeNode(60000);
System.out.println("Naive check: " + naiveCheck(root)); // true (WRONG)
System.out.println("Correct: " + isValidBST(root)); // false
}
static boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
static boolean validate(TreeNode n, long lo, long hi) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return validate(n.left, lo, n.val) && validate(n.right, n.val, hi);
}
}
Naive check: true
Correct: false
How do the bounds tighten during recursion?
The root starts with bounds (negative infinity, positive infinity). When you go left, the current value becomes the new upper bound because everything in the left subtree must be smaller. When you go right, the current value becomes the new lower bound because everything in the right subtree must be larger.
package com.bank.tree;
public class BoundsTrace {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { this.val = v; }
}
static boolean validateTrace(TreeNode node, long lo, long hi, String path) {
if (node == null) return true;
System.out.println(path + "node=" + node.val
+ " bounds=(" + lo + ", " + hi + ")"
+ (node.val <= lo || node.val >= hi ? " VIOLATION" : " OK"));
if (node.val <= lo || node.val >= hi) return false;
return validateTrace(node.left, lo, node.val, path + "L->")
&& validateTrace(node.right, node.val, hi, path + "R->");
}
public static void main(String[] args) {
TreeNode root = new TreeNode(50000);
root.left = new TreeNode(30000);
root.right = new TreeNode(70000);
root.left.left = new TreeNode(20000);
root.left.right = new TreeNode(40000);
validateTrace(root, Long.MIN_VALUE, Long.MAX_VALUE, "");
}
}
node=50000 bounds=(-9223372036854775808, 9223372036854775807) OK
L->node=30000 bounds=(-9223372036854775808, 50000) OK
L->L->node=20000 bounds=(-9223372036854775808, 30000) OK
L->R->node=40000 bounds=(30000, 50000) OK
R->node=70000 bounds=(50000, 9223372036854775807) OK
Why use Long instead of Integer for bounds?
If the tree contains Integer.MIN_VALUE or Integer.MAX_VALUE as node values, using int bounds causes false failures because the node value would equal the sentinel. Using long sentinels avoids this edge case.
package com.bank.tree;
public class LongBoundsEdge {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { this.val = v; }
}
// Using int bounds: FAILS for Integer.MIN_VALUE node
static boolean validateInt(TreeNode n, int lo, int hi) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return validateInt(n.left, lo, n.val) && validateInt(n.right, n.val, hi);
}
// Using long bounds: CORRECT
static boolean validateLong(TreeNode n, long lo, long hi) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return validateLong(n.left, lo, n.val) && validateLong(n.right, n.val, hi);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(Integer.MIN_VALUE);
System.out.println("Int bounds: " + validateInt(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
System.out.println("Long bounds: " + validateLong(root, Long.MIN_VALUE, Long.MAX_VALUE));
}
}
Int bounds: false
Long bounds: true
What is the inorder traversal alternative?
An inorder traversal of a valid BST produces values in strictly increasing order. You can validate the tree by performing an inorder traversal and checking that each value is strictly greater than the previous one.
package com.bank.tree;
public class InorderValidation {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int v) { this.val = v; }
}
private static long prev = Long.MIN_VALUE;
public static boolean isValidBSTInorder(TreeNode node) {
if (node == null) return true;
if (!isValidBSTInorder(node.left)) return false;
if (node.val <= prev) return false;
prev = node.val;
return isValidBSTInorder(node.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(50000);
root.left = new TreeNode(30000);
root.right = new TreeNode(70000);
prev = Long.MIN_VALUE;
System.out.println("Valid: " + isValidBSTInorder(root));
}
}
Valid: true
What is the time and space complexity?
| Metric | Bounds Approach | Inorder Approach |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(h) recursion stack | O(h) recursion stack |
| Early termination | Yes, on first violation | Yes, on first violation |
| Extra state | None (bounds are parameters) | Previous value variable |
How is this used in a banking system?
At the National Bank of India, account records are indexed in a BST by account number for fast lookup. After a bulk insert, the tree must be validated. A single misplaced record silently breaks every future lookup. The bounds-based validation catches exactly the dangerous case where a record satisfies its immediate parent but violates an ancestor's range.
package com.bank.tree;
public class BankAccountBST {
static class AccountNode {
long accountNumber;
String name;
AccountNode left, right;
AccountNode(long num, String name) {
this.accountNumber = num;
this.name = name;
}
}
static boolean validateAccounts(AccountNode node, long lo, long hi) {
if (node == null) return true;
if (node.accountNumber <= lo || node.accountNumber >= hi) {
System.out.println("INVALID: " + node.accountNumber
+ " outside (" + lo + ", " + hi + ")");
return false;
}
return validateAccounts(node.left, lo, node.accountNumber)
&& validateAccounts(node.right, node.accountNumber, hi);
}
public static void main(String[] args) {
AccountNode root = new AccountNode(50000, "Rajesh");
root.left = new AccountNode(30000, "Priya");
root.right = new AccountNode(70000, "Pankaj");
root.left.right = new AccountNode(60000, "Invalid"); // violates!
boolean valid = validateAccounts(root, Long.MIN_VALUE, Long.MAX_VALUE);
System.out.println("Account tree valid: " + valid);
}
}
INVALID: 60000 outside (-9223372036854775808, 50000)
Account tree valid: false
What are common interview follow-up questions?
- Interviewers frequently ask:
- Can you do it iteratively? (Yes, use a stack with bounds tuples.)
- What if duplicates are allowed on one side? (Adjust the comparison to allow equality on the chosen side.)
- How do you find the lowest common ancestor in a BST? (Use the BST property to decide left or right.)
- How do you convert a sorted array to a balanced BST? (Pick the middle element as root, recurse on halves.)
Visual Overview
Valid BST with bounds:
50000
(-inf, +inf)
/ \
30000 70000
(-inf, 50000) (50000, +inf)
/ \ \
20000 40000 80000
(-inf,30K) (30K,50K) (70K,+inf)
Invalid case (60000 in left subtree):
50000
(-inf, +inf)
/ \
30000 70000
(-inf, 50000)
\
60000
(30000, 50000) <-- 60000 > 50000: VIOLATION!
Key Takeaway
Validating a binary search tree is a problem where the obvious approach is wrong. The naive check of comparing each node only to its immediate children misses the global invariant: every node must be greater than all values in its left subtree and less than all values in its right subtree, across the entire subtree, not just the neighbors.
The correct approach threads a valid open interval down the recursion. Each node receives a lower and upper bound and must lie strictly between them. Going left sets the current value as the new upper bound, and going right sets it as the new lower bound. Using Long sentinels avoids edge cases at integer extremes.
An elegant alternative is the inorder traversal: a valid BST produces strictly increasing values when traversed inorder, so you validate by checking each value exceeds the previous. Both approaches are O(n) time and O(h) space.
In a banking system at the National Bank of India, account records indexed in a BST must be validated after bulk inserts. The bounds-based validation catches the dangerous case where a record satisfies its parent but violates an ancestor's range, which a naive neighbor check would miss.
Remember one sentence: thread a shrinking (lower, upper) interval down the recursion, and any node outside its inherited bounds proves the tree is not a valid BST.
---