Check if a binary tree is a binary search tree or not

Question

This checks if both the left and right subtrees are binary search trees. If they are, then it compares the nodes data with the maximum element in the nodes' left subtree and minimum element in the nodes' right sub tree.

class Node{
 int data;
 Node left;
 Node right;
 Node(int x){
 data = x;
 }
}
public class isBST {
 public static Node getMin(Node root)
 {
 while(root.left != null)
 {
 root = root.left;
 }
 return root;
 }
 public static Node getMax(Node root)
 {
 while(root.right != null)
 {
 root = root.right;
 }
 return root;
 }
 public static boolean isBST(Node root)
 {
 // for null node
 if(root == null )
 {
 return true;
 }
 // for single node
 if(root.left == null && root.right == null)
 {
 return true;
 }
 // for a non null node
 if(isBST(root.left ) && isBST(root.right) )
 {
 if(root.left != null && root.right != null)
 {
 return root.data < getMin(root.right).data && root.data > getMax(root.left).data;
 }
 else 
 {
 if(root.left != null)
 {
 return root.data > getMax(root.left).data;
 }
 else
 {
 return root.data < getMin(root.right).data;
 }
 }
 }
 else
 {
 return false;
 } 
 }
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 Node root = new Node(5);
 root.left = new Node(3);
 root.right = new Node(7);
 root.left.left = new Node(2);
 root.left.right = new Node(4);
 root.right.left = new Node(6);
 root.right.right = new Node(9);
 System.out.println(isBST(root));
 }
}

Answer 1

Some quick notes:

• Respect "Egyptian Braces" for your block structures (if, while, ...) i.e., the opening brace should be on the same line as the signature statement. The style you used (opening brace on a new line) is ordinarily used for C#, not Java.

• Node could and should be as immutable as possible:

  class Node {
   final int data;
   Node left;
   Node right;
   Node (int x) {
   data = x;
   }
  }
  

• isBST is not a good class name. Class names are usually nouns. I'd suggest (as was already in the currently deleted other answer) BinarySearchTreeUtil.

• getMin and getMax are factually only correct if you assume that the Tree is actually a BST. Only checking for those two is not a sufficient indicator, though. A BST is only fully a BST if each and every node satisfies the condition you propose. Your code does not check for that.

  You should instead verify that each subtree is a BST recursively. Aside from that you're also assuming that the BST is ordered with the smaller elements to the left. It's also correct for a BST to be ordered with smaller elements to the right. Your code doesn't deal with that either.

Overall your code does not correctly solve the problem. To remedy this I strongly suggest you invest some time into unit-testing your code. Furthermore, you're disregarding conventions about bracing (but you're consistent so it's somewhat acceptable), as well as class-names (that's not acceptable).