Valid BST Or Not Algorithm
The Valid BST (Binary Search Tree) or Not Algorithm is a verification algorithm used to determine whether a given binary tree satisfies the properties of a Binary Search Tree or not. A Binary Search Tree (BST) is a binary tree data structure where each node has at most two children, and for each node, the left subtree has nodes containing values less than the node's value, and the right subtree has nodes containing values greater than the node's value. Essentially, the algorithm checks for the adherence of the binary tree to these conditions and returns a boolean value indicating the validity of the BST.
To implement the Valid BST or Not Algorithm, a recursive approach is often employed. Starting from the root node, the algorithm checks if the node's value lies within a specified range. If the node satisfies the range constraint, the algorithm proceeds to check the left and right subtrees recursively, updating the range for each subtree accordingly. The base case for the recursion occurs when an empty tree or a single node tree is encountered, which is considered a valid BST. If all nodes satisfy the range constraint, the algorithm returns true, indicating that the given binary tree is a valid BST; otherwise, it returns false. This algorithm's time complexity is O(n), where n is the number of nodes in the binary tree, as each node is visited once during the traversal.
package DataStructures.Trees;
public class ValidBSTOrNot {
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
//Root of the Binary Tree
/* can give min and max value according to your code or
can write a function to find min and max value of tree. */
/* returns true if given search tree is binary
search tree (efficient version) */
boolean isBST(Node root) {
return isBSTUtil(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
/* Returns true if the given tree is a BST and its
values are >= min and <= max. */
boolean isBSTUtil(Node node, int min, int max) {
/* an empty tree is BST */
if (node == null)
return true;
/* false if this node violates the min/max constraints */
if (node.data < min || node.data > max)
return false;
/* otherwise check the subtrees recursively
tightening the min/max constraints */
// Allow only distinct values
return (isBSTUtil(node.left, min, node.data - 1) &&
isBSTUtil(node.right, node.data + 1, max));
}
}
