42 / 75
DFS with min/max bounds: left subtree < node < right subtree, recursively validate.
Example:
Input:
root=[5,1,4,null,null,3,6]Output:
false (3 is in right subtree but < 5)Common Mistakes:
- Only checking node.left < node < node.right (ignores subtree constraints)
- Not passing bounds down recursion tree
- Using int instead of Integer (causes issues with Integer.MIN_VALUE)
- Forgetting that BST doesn't allow duplicate values (use < and >, not <= and >=)
Notes:
Must validate entire subtree constraints, not just immediate children. Time O(n), Space O(h). Alternative: inorder traversal should be strictly increasing.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
DFS with min/max bounds: left subtree < node < right subtree, recursively validate.
Example:
Input:
root=[5,1,4,null,null,3,6]Output:
false (3 is in right subtree but < 5)Common Mistakes:
- Only checking node.left < node < node.right (ignores subtree constraints)
- Not passing bounds down recursion tree
- Using int instead of Integer (causes issues with Integer.MIN_VALUE)
- Forgetting that BST doesn't allow duplicate values (use < and >, not <= and >=)
Notes:
Must validate entire subtree constraints, not just immediate children. Time O(n), Space O(h). Alternative: inorder traversal should be strictly increasing.
42/75
Validate Binary Search Tree