Validate Binary Search Tree

Problem
Given the root
of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
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 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
The number of nodes in the tree is in the range
[1, 10<sup>4</sup>]
.-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1
Solution
Idea: We need to use the property of the binary search tree, where the left child is less than the parent, and the parent is less than the right child. This rule must apply to all ancestors and descendants. In other words, any left grandchild should be less than any parent, and any right grandchild should be greater than any parent. Therefore, we must always consider the minimum and maximum values of the ancestors to ensure the current node falls within the correct range.
Time - O(n)
Space - O(n), Auxiliary space (generally it will be the height of the BST)
class Solution {
private boolean isValid(TreeNode root, long min, long max){
if(root == null) return true;
if(root.val<=min || root.val>=max) return false;
return isValid(root.left, min, root.val)
&& isValid(root.right, root.val, max);
}
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
Subscribe to my newsletter
Read articles from Chetan Datta directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Chetan Datta
Chetan Datta
I'm someone deeply engrossed in the world of software developement, and I find joy in sharing my thoughts and insights on various topics. You can explore my exclusive content here, where I meticulously document all things tech-related that spark my curiosity. Stay connected for my latest discoveries and observations.