Binary Search TreesProblem 5 of 22
Check if a tree is a BST or not
Problem Statement
Given a binary tree, determine if it is a valid Binary Search Tree (BST). A valid BST is defined as:
- The left subtree of a node contains only nodes with keys less than the node's key
- The right subtree of a node contains only nodes with keys greater than the node's key
- Both the left and right subtrees must also be binary search trees
Example:
Valid BST: Invalid BST:
5 5
/ \ / \
3 7 3 7
/ \ \ / \ \
1 4 9 1 6 9
^ (6 > 5 but in left subtree)
Approach 1: Brute Force (Check Each Node Against All)
Intuition
For each node, check if all values in left subtree are smaller and all values in right subtree are larger. This requires traversing subtrees for each node.
Algorithm
- For each node, traverse entire left subtree to check all values are smaller
- Traverse entire right subtree to check all values are larger
- Recursively verify subtrees
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int findMax(TreeNode root) {
if (root == null) return Integer.MIN_VALUE;
return Math.max(root.val, Math.max(findMax(root.left), findMax(root.right)));
}
private int findMin(TreeNode root) {
if (root == null) return Integer.MAX_VALUE;
return Math.min(root.val, Math.min(findMin(root.left), findMin(root.right)));
}
public boolean isValidBSTBruteForce(TreeNode root) {
if (root == null) return true;
// Check if max in left subtree is less than root
if (root.left != null && findMax(root.left) >= root.val) {
return false;
}
// Check if min in right subtree is greater than root
if (root.right != null && findMin(root.right) <= root.val) {
return false;
}
// Recursively check subtrees
return isValidBSTBruteForce(root.left) && isValidBSTBruteForce(root.right);
}
}Complexity Analysis
- Time Complexity: O(n^2) - For each node, we traverse its subtree
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (Range-Based Validation)
Intuition
Instead of checking subtrees for each node, pass down valid range constraints. Each node must fall within a valid range, and we update the range as we go deeper.
Algorithm
- Start with range (-∞, +∞) for root
- For left child, update upper bound to parent's value
- For right child, update lower bound to parent's value
- If any node violates its range, return false
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private boolean isValidBSTHelper(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
// Check if current node violates the range
if (root.val <= minVal || root.val >= maxVal) {
return false;
}
// Recursively validate subtrees with updated ranges
return isValidBSTHelper(root.left, minVal, root.val) &&
isValidBSTHelper(root.right, root.val, maxVal);
}
public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - Recursion stack in worst case
Approach 3: Optimal (Inorder Traversal)
Intuition
Inorder traversal of a valid BST produces a strictly increasing sequence. We can verify this property during traversal.
Algorithm
- Perform inorder traversal
- Keep track of previously visited node
- If current value is not greater than previous, it's not a valid BST
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode prev = null;
public boolean isValidBST(TreeNode root) {
prev = null;
return inorderValidate(root);
}
private boolean inorderValidate(TreeNode root) {
if (root == null) return true;
// Check left subtree
if (!inorderValidate(root.left)) return false;
// Check current node against previous
if (prev != null && root.val <= prev.val) {
return false;
}
prev = root;
// Check right subtree
return inorderValidate(root.right);
}
// Iterative version
public boolean isValidBSTIterative(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (prev != null && curr.val <= prev.val) {
return false;
}
prev = curr;
curr = curr.right;
}
return true;
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - Stack space
Key Takeaways
- Common mistake: Only checking immediate children, not entire subtrees
- Range approach: Pass down valid ranges - elegant and efficient
- Inorder approach: BST inorder is strictly increasing
- Use long: To handle INT_MIN and INT_MAX edge cases
- This is LeetCode #98 - Validate Binary Search Tree
- Three valid approaches: range-based, inorder recursive, inorder iterative
- All optimal approaches are O(n) time