Is Binary search tree - Java Program
/**
* Following method can be used to test if a tree meets the conditions to be a binary search tree (BST).
*/
public boolean isBST(TreeNode root) {
if (root == null)
return false;
return( isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );
}
/**
* Recursive Method - which validates very sub tree of a given binary tree.
* Works in O(n) time -- visits each node only once.
* @param min For left sub tree it should be Integer.MIN_Value
* For right sub tree it should be node.data + 1
* @param max For left sub tree it should be node.data
* For right sub tree it should be Integer.MAX_VALUE
*
*/
private boolean isBST2(TreeNode node, int min, int max) {
if (node==null) {
return(true);
}
else {
if (node.getData() < min || node.getData() > max)
return false;
// left should be in range min...node.data
boolean leftOk = isBST(node.getLeft(), min, node.getData());
// if the left is not ok, bail out
if (!leftOk) return(false);
// right should be in range node.data+1..max
boolean rightOk = isBST(node.getRight(), node.getData()+1, max);
return(rightOk);
}
}
* Following method can be used to test if a tree meets the conditions to be a binary search tree (BST).
*/
public boolean isBST(TreeNode root) {
if (root == null)
return false;
return( isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );
}
/**
* Recursive Method - which validates very sub tree of a given binary tree.
* Works in O(n) time -- visits each node only once.
* @param min For left sub tree it should be Integer.MIN_Value
* For right sub tree it should be node.data + 1
* @param max For left sub tree it should be node.data
* For right sub tree it should be Integer.MAX_VALUE
*
*/
private boolean isBST2(TreeNode node, int min, int max) {
if (node==null) {
return(true);
}
else {
if (node.getData() < min || node.getData() > max)
return false;
// left should be in range min...node.data
boolean leftOk = isBST(node.getLeft(), min, node.getData());
// if the left is not ok, bail out
if (!leftOk) return(false);
// right should be in range node.data+1..max
boolean rightOk = isBST(node.getRight(), node.getData()+1, max);
return(rightOk);
}
}
This comment has been removed by the author.
ReplyDelete