How to check if a Binary Tree is BST or not?

What is Binary Search Tree(BST)?

A binary search tree (BST) is a node based binary tree data structure.

Must have these 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.

Implementation:

/**

 * 

 */

package com.bst;

/**

 * @author Abhinaw.Tripathi

 *

 */

class Node

{

int data;

Node left,right;

public Node(int item)

{

this.data=item;

left=right=null;

}

}

public class BinaryTree

{

/**

* 

*/

private Node root;

public BinaryTree() 

{

// TODO Auto-generated constructor stub

}

public boolean isBSTUtil(Node node,int min,int max)

{

if(node == null)

return true;

if(node.data < min || node.data> max)

return false;

return (isBSTUtil(node.left, min, node.data-1) && isBSTUtil(node.right, node.data+1, max));

}

public boolean isBST()  

{

        return isBSTUtil(root, Integer.MIN_VALUE,Integer.MAX_VALUE);

    }

 

/**

* @param args

*/

public static void main(String[] args) 

{

// TODO Auto-generated method stub

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");

        }

}

}

Time Complexity: O(n)

Auxiliary Space : O(1) 

If Function Call Stack size is not valid, otherwise O(n)