Validate Binary Search Tree
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, 104]. -
-231 <= Node.val <= 231 - 1
Solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right)
{
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isBST(root, Long.MIN_VALUE,
Long.MAX_VALUE);
}
boolean isBST(TreeNode node, long min, long max)
{
if (node == null)
return true;
if (node.val <= min || node.val >=
max)
return false;
return (isBST(node.left, min, node.val)
&&
isBST(node.right,
node.val, max));
}
}
A Tree is said to be Binary Search Tree if left nodes of the tree are lesser
than root value and right nodes of the tree are greater than root value.
[Check above example inputs]
Here, at each node we are going to compare each node value with its parent
node min and max value.
1) Initially to fix min and max we are using Long.MIN_VALUE and
Long.MAX_VALUE.
2) Recursively we are going to iterate both left and right tree
by changing its min and max value depends on the traversing
side.
3) Recursively iterate the left subtree by changing its
max value with node.val (i.e., isBST(node.left, min, node.val) )
4) Recursively iterate the right subtree by changing its
min value with node.val (i.e., isBST(node.right, node.val, max)
)
5) Repeat above steps for the entire tree. If any of the
node value is less than or equal to min or greater than or equal to max
, then return false.
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section which will be helpful for us to improve.
Comments
Post a Comment