Binary Search Tree

This tutorial will check if a Binary Tree is Binary Search Tree or not. It is known that a binary search tree (BST) is a node based binary tree data structure which satisfies the following properties:

• The left sub-tree of a node contains only nodes with keys less than the root node’s key.
• The right sub-tree of a node contains only nodes with keys greater than the root node’s key.
• Both the left and right sub-trees must also be again binary search trees.

I will implement the algorithm using Java program in O(n) time complexity to check whether the Binary Tree is Binary Search Tree or not.

Prerequisite

Knowledge of Java

Binary Search Tree Check

The following Java source code will check if a binary tree is binary search tree (BST) or not.

public class BinaryTree {
	Node root;
	Node prev;
	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		binaryTree.root = binaryTree.new Node(5);
		binaryTree.root.left = binaryTree.new Node(3);
		binaryTree.root.right = binaryTree.new Node(6);
		binaryTree.root.left.left = binaryTree.new Node(1);
		binaryTree.root.left.right = binaryTree.new Node(2);
		System.out.println(binaryTree.isBST(binaryTree.root));
	}
	private boolean isBST(Node node) {
		if (node != null) {
			if (!isBST(node.left)) {
				return false;
			}
			if (prev != null && node.data <= prev.data) {
				return false;
			}
			prev = node;
			return isBST(node.right);
		}
		return true;
	}
	private class Node {
		int data;
		Node left, right;
		public Node(int data) {
			this.data = data;
			this.left = this.right = null;
		}
	}
}

In the above class I have used recursive function to check if a binary tree is binary search tree or not.

Testing Binary Search Tree

Please run the above class, you should see the following output:

false

Therefore the above binary tree is not a binary search tree.

Now replace

binaryTree.root.left.right = binaryTree.new Node(2);

by

binaryTree.root.left.right = binaryTree.new Node(4);

and run the above code again, you should see the following output:

true

Source Code

Download