# Program: How to check the given Binary Tree is Binary Search Tree (BST) or not?

 Description: In a Binary Tree, each node can have at most two nodes. For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater than the data of the root. There are various ways to validate Binary Search Tree. One of the simple way is: The in-order traversal of a binary search tree results natural order. So, we can do in-order traversal and check for natural order. If the order sorted, then it is binary search tree. We will give this implementation in the coming pages. In this page we follow different approach. We will set min and max value for each node and validate node data against min and max value. The same approach will continue for each left and right sub binary search tree in recursive way. Here is the steps to validate binary search tree: Start with root node. In this case root node data min & max values can be extreme integer ranges. Pass min value as Integer.MIN_VALUE and max value as Integer.MAX_VALUE. Make sure node data is falling under min & max values. Along with the above check, make sure the left and right sub trees are also go through similar checks. Make a recursive call on left node with no change in min value and node data as max value. Make a recursive call on right node with node data as min value and no change in max value. Check the the code for better understanding.

 IsBinarySearchTree ```package com.java2novice.ds; public class IsBinarySearchTree { public boolean isBinarySearchTree(BstNode root) { if(root == null) return Boolean.TRUE; return isBstValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isBstValid(BstNode root, Integer minValue, Integer maxValue) { if(root == null) return Boolean.TRUE; if(root.getData() >= minValue && root.getData() < maxValue && isBstValid(root.getLeft(), minValue, root.getData()) && isBstValid(root.getRight(), root.getData(), maxValue)) { return Boolean.TRUE; } else { return Boolean.FALSE; } } } ```

 BstNode ```package com.java2novice.ds; public class BstNode { private BstNode left; private BstNode right; private Integer data; public BstNode(Integer data) { this.data = data; } public BstNode getLeft() { return left; } public void setLeft(BstNode left) { this.left = left; } public BstNode getRight() { return right; } public void setRight(BstNode right) { this.right = right; } public Integer getData() { return data; } } ```

 Input Tree: ``` 3 / \ 2 6 / \ / \ 1 4 5 7 ```

 Input Tree in main method: ``` public static void main(String a[]) { BstNode root = new BstNode(3); // left sub tree BstNode node_2 = new BstNode(2); root.setLeft(node_2); BstNode node_1 = new BstNode(1); node_2.setLeft(node_1); BstNode node_4 = new BstNode(4); node_2.setRight(node_4); // right sub tree BstNode node_6 = new BstNode(6); root.setRight(node_6); BstNode node_5 = new BstNode(5); node_6.setLeft(node_5); BstNode node_7 = new BstNode(7); node_6.setRight(node_7); IsBinarySearchTree ibsTree = new IsBinarySearchTree(); System.out.println(ibsTree.isBinarySearchTree(root)); } ```

 Output: `false`

 Input Tree: ``` 8 / \ 3 10 / \ \ 1 6 14 ```

 Input Tree in main method: ``` public static void main(String a[]) { BstNode root = new BstNode(8); // left sub tree BstNode node_3 = new BstNode(3); root.setLeft(node_3); BstNode node_1 = new BstNode(1); node_3.setLeft(node_1); BstNode node_6 = new BstNode(6); node_3.setRight(node_6); // right sub tree BstNode node_10 = new BstNode(10); root.setRight(node_10); BstNode node_14 = new BstNode(14); node_10.setRight(node_14); IsBinarySearchTree ibsTree = new IsBinarySearchTree(); System.out.println(ibsTree.isBinarySearchTree(root)); } ```

 Output: `true`

#### List Of All Interview Programs:

Knowledge Centre
Stream and types of Streams
A Stream is an abstraction that either produces or consumes information. There are two types of Streams and they are:

Byte Streams: Provide a convenient means for handling input and output of bytes. Byte Streams classes are defined by using two abstract classes, namely InputStream and OutputStream.

Character Streams: Provide a convenient means for handling input & output of characters. Character Streams classes are defined by using two abstract classes, namely Reader and Writer.
Famous Quotations
Do not confuse motion and progress. A rocking horse keeps moving but does not make any progress.
-- Alfred A. Montapert