Skip to content

Instantly share code, notes, and snippets.

@thmain
Created Jan 19, 2016
Embed
What would you like to do?
public class isBST {
public static Node prevNode = null;
// method 1: do inOrder and check if it is in ascending order
// doesnt work in case of duplicates
public boolean isBST1(Node root) {
if (root != null) {
if (!isBST1(root.left))
return false;
if (prevNode != null && prevNode.data >= root.data) {
return false;
}
prevNode = root;
return isBST1(root.right);
}
return true;
}
// //method 2
// The max-Min solution
public boolean isBST2(Node root, int min, int max) {
if (root != null) {
if (root.data > max || root.data < min) {
return false;
}
return isBST2(root.left, min, root.data)
&& isBST2(root.right, root.data, max);
} else {
return true;
}
}
public void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(" " + root.data);
inorder(root.right);
}
}
public static void main(String args[]) {
isBST i = new isBST();
Node root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);
root.right.left = new Node(25);
root.right.right = new Node(35);
System.out.println("Tree is ");
i.inorder(root);
System.out.println();
System.out.println("is Tree BST ?? METHOD 1 : " + i.isBST1(root));
System.out.println("is Tree BST ?? METHOD 2 : "
+ i.isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
root.left.right.right = new Node(40);
System.out.println("Tree is ");
i.inorder(root);
System.out.println();
System.out.println("is Tree BST ?? METHOD 1 : " + i.isBST1(root));
System.out.println("is Tree BST ?? METHOD 2 : "
+ i.isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment