# Check if a Binary Tree is a Binary Search Tree (BST) using Property of Binary Tree

### Approach

• For a BST, all left nodes should be less than or equal to current node and current node must be less than all right nodes.

• We will have a recursive function that checks if this property is true for every node and all its sub trees:

• If the method get null node, it may return true, and should be first checked (exit condition for the recursion).

• Check if 'left nodes is less than or equal to current node and current node must be less than all right nodes.

• Then call the method for subtrees and see if the follow the property of BST

### Solution

checkIfBST(TNode n, int min, int max)

{

if(n==null)

return true;

if(n.data <=min || n.data > right)

return false;

boolean leftIsBST = checkIfBST(n.left, min, n.data);

if(!leftIsBST)

return false;

boolean rightIsBST = checkIfBST(n.right, n.data, max);

if(!rightIsBST)

return false;

return true;

}

The recursive function will be initially passed with the root node, Integer.MIN_VALUE and Integer.MAX_VALUE.

• E.g. checkIfBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

### Complexity

Time complexity is O(N)

Space complexity is O(log N)