Binary Search Tree (BST):

A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• 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.

From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.

Java program to check if a binary tree is BST:

METHOD 1 (Correct and Efficient):

A better solution looks at each node only once. The trick is to write a utility helper function is BST Util(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.

/* Returns true if the given tree is a binary search tree 
 (efficient version). */ 
int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
 values are >= min and <= max. */ 
int isBSTUtil(struct node* node, int min, int max)

Implementation:

[pastacode lang=”java” manual=”%2F%2FJava%20implementation%20to%20check%20if%20given%20Binary%20tree%0A%2F%2Fis%20a%20BST%20or%20not%0A%20%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20left%2C%20right%3B%0A%20%0A%20%20%20%20public%20Node(int%20item)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20item%3B%0A%20%20%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Apublic%20class%20BinaryTree%0A%7B%0A%20%20%20%20%0A%20%20%20%20Node%20root%3B%0A%20%0A%20%20%20%20%0A%20%20%20%20boolean%20isBST()%20%20%7B%0A%20%20%20%20%20%20%20%20return%20isBSTUtil(root%2C%20Integer.MIN_VALUE%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Integer.MAX_VALUE)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%0A%20%20%20%20boolean%20isBSTUtil(Node%20node%2C%20int%20min%2C%20int%20max)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(node%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(node.data%20%3C%20min%20%7C%7C%20node.data%20%3E%20max)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20(isBSTUtil(node.left%2C%20min%2C%20node.data-1)%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20isBSTUtil(node.right%2C%20node.data%2B1%2C%20max))%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20BinaryTree%20tree%20%3D%20new%20BinaryTree()%3B%0A%20%20%20%20%20%20%20%20tree.root%20%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20%20tree.root.left%20%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20%20tree.root.right%20%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20tree.root.left.left%20%3D%20new%20Node(1)%3B%0A%20%20%20%20%20%20%20%20tree.root.left.right%20%3D%20new%20Node(3)%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(tree.isBST())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22IS%20BST%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Not%20a%20BST%22)%3B%0A%20%20%20%20%7D%0A%7D” message=”Java Programming” highlight=”” provider=”manual”/]

Output: 

IS BST

Time Complexity: O(n)
Auxiliary Space : O(1) if Function Call Stack size is not considered, otherwise O(n)

[ad type=”banner”]

Java program to check if a binary tree is BST:

METHOD 2(Using In-Order Traversal):

1) Do In-Order Traversal of the given tree and store the result in a temp array.
2) Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

Time Complexity: O(n)

We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST.

Implementation:

[pastacode lang=”java” manual=”%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20left%2C%20right%3B%0A%20%0A%20%20%20%20public%20Node(int%20item)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20item%3B%0A%20%20%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Apublic%20class%20BinaryTree%0A%7B%0A%20%20%20%0A%20%20%20%20Node%20root%3B%0A%20%0A%20%20%0A%20%20%20%20Node%20prev%3B%0A%20%0A%20%20%20%20boolean%20isBST()%20%20%7B%0A%20%20%20%20%20%20%20%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20return%20isBST(root)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%0A%20%20%20%20boolean%20isBST(Node%20node)%0A%20%20%20%20%7B%0A%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20(node%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!isBST(node.left))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(prev%20!%3D%20null%20%26%26%20node.data%20%3C%3D%20prev.data%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20node%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20isBST(node.right)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20BinaryTree%20tree%20%3D%20new%20BinaryTree()%3B%0A%20%20%20%20%20%20%20%20tree.root%20%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20%20tree.root.left%20%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20%20tree.root.right%20%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20tree.root.left.left%20%3D%20new%20Node(1)%3B%0A%20%20%20%20%20%20%20%20tree.root.left.right%20%3D%20new%20Node(3)%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(tree.isBST())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22IS%20BST%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Not%20a%20BST%22)%3B%0A%20%20%20%20%7D%0A%7D” message=”Java Programming” highlight=”” provider=”manual”/] [ad type=”banner”]

Output: 

IS BST