Java Program to check if a given binary tree is BST or not?

In this post, We will talk and learn How to write a Java Program to check if a given binary tree is BST(Binary Search Tree) or not?

Binary Search Tree (BST) Data Structure

Binary Search Tree or BST is a node-based binary tree data structure which are having the following properties:

The left subtree of a node contains only nodes with values smaller value than the root node’s value.
The right subtree of a node contains only nodes with values greater than the root node’s value.
The left and right subtrees are also must be a binary search tree.
You should note that Binary Search Tree(BST) must not be duplicate nodes.

Below is the Complete Source code:

BinaryTree.java

package com.kkjavatutorials.tree;

public class BinaryTree<E extends Comparable<? super E>> {
	
	/**
	 * This internal class represents Node of Binary tree
	 * @author KK JavaTutorials
	 */
	public static class Node<T> {
		
		//Data hold by Binary Tree Node
		public T data;
		
		//Left pointer/reference
		public Node<T> left;
		
		//Right pointer/reference
		public Node<T> right;

		public Node(T data) {
			this.data = data;
		}
	}
	
	/**
	 * Recursive method for Binary Tree
	 * inOrder Processing
	 * @param root Node
	 */
	public void inOrder(Node<E> root) {
		if(root != null) {
		inOrder(root.left);
		System.out.print(root.data+" ");
		inOrder(root.right);
		}
	}

	/**
	 * Function to check whether given input
	 * Binary Tree is BST(Binary Search Tree) or Not?
	 * @param root Binary Tree
	 * @return true if input Binary Tree
	 * is BST(Binary Search Tree)
	 */
	public boolean isBinaryTreeBST(Node<Integer> root) {
		
		//Empty Tree is also valid BST
		if(root == null)
			return true;
		
		//If Left Node's value is greater than root
		if(root.left != null && root.left.data > root.data)
			return false;
		
		//If Right Node's value is smaller than root
		if(root.right != null && root.right.data < root.data)
			return false;
		
		//Call recursively isBinaryTreeBST for Left and Right sub trees
		if(!isBinaryTreeBST(root.left) || !isBinaryTreeBST(root.right))
			return false;
		
		return true;
	}
}

package com.kkjavatutorials.tree;

public class BinaryTree<E extends Comparable<? super E>> {

/**

* This internal class represents Node of Binary tree

* @author KK JavaTutorials

public static class Node<T> {

//Data hold by Binary Tree Node

public T data;

//Left pointer/reference

public Node<T> left;

//Right pointer/reference

public Node<T> right;

public Node(T data) {

this.data = data;

}

/**

* Recursive method for Binary Tree

* inOrder Processing

* @param root Node

public void inOrder(Node<E> root) {

if(root != null) {

inOrder(root.left);

System.out.print(root.data+" ");

inOrder(root.right);

}

/**

* Function to check whether given input

* Binary Tree is BST(Binary Search Tree) or Not?

* @param root Binary Tree

* @return true if input Binary Tree

* is BST(Binary Search Tree)

public boolean isBinaryTreeBST(Node<Integer> root) {

//Empty Tree is also valid BST

if(root == null)

return true;

//If Left Node's value is greater than root

if(root.left != null && root.left.data > root.data)

return false;

//If Right Node's value is smaller than root

if(root.right != null && root.right.data < root.data)

return false;

//Call recursively isBinaryTreeBST for Left and Right sub trees

if(!isBinaryTreeBST(root.left) || !isBinaryTreeBST(root.right))

return false;

return true;

}

ClientTest.java

package com.kkjavatutorials.client;

import com.kkjavatutorials.tree.BinaryTree;
import com.kkjavatutorials.tree.BinaryTree.Node;
/**
 * Client Program to check if a given binary tree
 * is BST(Binary Search Tree) or not?
 * @author KK JavaTutorials
 */
public class ClientTest {

	public static void main(String[] args) {

		// Root Node
		Node<Integer> rootNode = new Node<Integer>(10);

		Node<Integer> secondNode = new Node<Integer>(5);
		Node<Integer> thirdNode = new Node<Integer>(19);
		Node<Integer> fourthNode = new Node<Integer>(1);
		Node<Integer> fifthNode = new Node<Integer>(6);
		Node<Integer> sixthNode = new Node<Integer>(17);
		Node<Integer> seventhNode = new Node<Integer>(21);

		// Setting Left and right of root Node
		rootNode.left = secondNode;
		rootNode.right = thirdNode;

		rootNode.left.left = fourthNode;
		rootNode.left.right = fifthNode;

		rootNode.right.left = sixthNode;
		rootNode.right.right = seventhNode;

		// Create an Instance of BinaryTree
		BinaryTree<Integer> binaryTree = new BinaryTree<>();

		System.out.println("InOrder Processing of Binary Tree::");
		binaryTree.inOrder(rootNode);

		System.out.println();
		boolean isBST = binaryTree.isBinaryTreeBST(rootNode);

		if (isBST)
			System.out.println("Input Binary Tree is BST");
		else
			System.out.println("Input Binary Tree is not BST");

	}
}

package com.kkjavatutorials.client;

import com.kkjavatutorials.tree.BinaryTree;

import com.kkjavatutorials.tree.BinaryTree.Node;

/**

* Client Program to check if a given binary tree

* is BST(Binary Search Tree) or not?

* @author KK JavaTutorials

public class ClientTest {

public static void main(String[] args) {

// Root Node

Node<Integer> rootNode = new Node<Integer>(10);

Node<Integer> secondNode = new Node<Integer>(5);

Node<Integer> thirdNode = new Node<Integer>(19);

Node<Integer> fourthNode = new Node<Integer>(1);

Node<Integer> fifthNode = new Node<Integer>(6);

Node<Integer> sixthNode = new Node<Integer>(17);

Node<Integer> seventhNode = new Node<Integer>(21);

// Setting Left and right of root Node

rootNode.left = secondNode;

rootNode.right = thirdNode;

rootNode.left.left = fourthNode;

rootNode.left.right = fifthNode;

rootNode.right.left = sixthNode;

rootNode.right.right = seventhNode;

// Create an Instance of BinaryTree

BinaryTree<Integer> binaryTree = new BinaryTree<>();

System.out.println("InOrder Processing of Binary Tree::");

binaryTree.inOrder(rootNode);

System.out.println();

boolean isBST = binaryTree.isBinaryTreeBST(rootNode);

if (isBST)

System.out.println("Input Binary Tree is BST");

else

System.out.println("Input Binary Tree is not BST");

}

The output of This Program:

InOrder Processing of Binary Tree::
1 5 6 10 17 19 21
Input Binary Tree is BST

You May Also Like:

Introduction to Tree Data Structure
Introduction to Binary Tree
Difference between binary and binary search trees
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Find the sum of all elements in Binary Tree
Find the height or depth of a binary tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
Find the node with minimum and maximum values in a Binary Search Tree
Find a mirror image of a binary tree
Find given two trees are mirror image or not
How do you find if two given binary trees are the same or identical
How to convert sorted Linked List to balanced Binary Search Tree?

That’s all about Java Program to check if a given binary tree is BST or not?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply Cancel reply