Check Bst

24 Jun 2019

// Java implementation to check if given Binary tree 
// is a BST or not 

/* Class containing left and right child of current 
   node and key value*/
class Node 
{ 
	int data; 
	Node left, right; 

	public Node(int item) 
	{ 
		data = item; 
		left = right = null; 
	} 
} 

public class BinaryTree 
{ 
	// Root of the Binary Tree 
	Node root; 

	// To keep tract of previous node in Inorder Traversal 
	Node prev; 

	boolean isBST() { 
		prev = null; 
		return isBST(root); 
	} 

	/* Returns true if given search tree is binary 
	   search tree (efficient version) */
	boolean isBST(Node node) 
	{ 
		// traverse the tree in inorder fashion and 
		// keep a track of previous node 
		if (node != null) 
		{ 
			if (!isBST(node.left)) 
				return false; 

			// allows only distinct values node 
			if (prev != null && node.data <= prev.data ) 
				return false; 
			prev = node; 
			return isBST(node.right); 
		} 
		return true; 
	} 

	/* Driver program to test above functions */
	public static void main(String args[]) 
	{ 
		BinaryTree tree = new BinaryTree(); 
		tree.root = new Node(4); 
		tree.root.left = new Node(2); 
		tree.root.right = new Node(5); 
		tree.root.left.left = new Node(1); 
		tree.root.left.right = new Node(3); 

		if (tree.isBST()) 
			System.out.println("IS BST"); 
		else
			System.out.println("Not a BST"); 
	} 
}