A binary search tree is a binary tree which has the following 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
From the above it’s clear that each node in the binary search tree will have distinct key.
The following two solutions can be used to check whether given binary tree is a binary search tree or not:
- For every node check whether its values is greater than maximum value of its left subtree and is less than minimum value of its right subtree
- Traverse down the tree by keeping allowable minimum and maximum at every node
Consider following binary tree which is a binary search tree.
For every node check whether its values is greater than maximum value of its left subtree and is less than minimum value of its right subtree
This solution runs slowly because it traverses over some parts of the tree many times as we need to calculate maximum value of left subtree and minimum value of right subtree every time. The next solution is more efficient than this.
Code for the above solution is as follows:
Implementation for Node, Tree, BinaryTree can be obtained from my previous post.
package ds;
public class ISBst
{
public ISBst()
{
}
// Returns true if a binary tree is a binary search tree
public boolean isBST(Node node)
{
// true for empty tree
if(node == null)
{
return true;
}
// false if the max of the left is > than current data
if(node.left != null && maxValue(node.left) > node.data)
{
return false;
}
System.out.println(node.data);
// false if the min of the right is <= than current data
if(node.right != null && minValue(node.right) <= node.data)
{
return false;
}
System.out.println(node.data);
// false if, recursively, the left or right is not a BST
if(!isBST(node.left) || !isBST(node.right))
{
return false;
}
// passing all that, it's a BST
return true;
}
public int maxValue(Node node)
{
while(node.right != null)
{
node = node.right;
}
return node.data;
}
public int minValue(Node node)
{
while(node.left != null)
{
node = node.left;
}
return node.data;
}
public static void main(String[] args)
{
/*
Constructing following tree
4
2 5
1 3 NA 7
*/
BinaryTree binaryTree = new BinaryTree();
binaryTree.create(4);
Node root = binaryTree.search(4);
binaryTree.add(root, 2, BinaryTree.LEFT);
binaryTree.add(root, 5, BinaryTree.RIGHT);
binaryTree.add(binaryTree.search(2), 1, BinaryTree.LEFT);
binaryTree.add(binaryTree.search(2), 3, BinaryTree.RIGHT);
binaryTree.add(binaryTree.search(5), 7, BinaryTree.RIGHT);
System.out.println("Binary Tree in level order is .... ");
binaryTree.printLevelOrder();
ISBst bTree = new ISBst();
if(bTree.isBST(root))
{
System.out.println("Given binary tree is a binary search tree");
}
else
{
System.out.println("Given binary tree is not a binary search tree");
}
}
}
Traverse down the tree by keeping allowable minimum and maximum at every node
This solution traverses down the tree from root and checks whether the current node lies between allowable minimum and maximum values. Initial values for minimum value and maximum value will be Integer.MIN_VALUE and Integer.MAX_VALUE. (If we feel our data doesn’t lie between the above values, we need to traverse over the binary tree once and get minimum value and maximum value).
Code for the above solution is as follows:
Implementation for Node, Tree, BinaryTree can be obtained from my previous post.
package ds;
public class IsBstEfficient
{
public IsBstEfficient()
{
}
public boolean isBST(Node node)
{
return (isBST(node, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
public boolean isBST(Node node, int minValue, int maxValue)
{
// True is its a empty tree
if(node == null)
{
return true;
}
// False if this node violates the BST property
if(node.data < minValue || node.data > maxValue)
{
return false;
}
// Otherwise check the subtree recursively
return (isBST(node.left, minValue, node.data) && isBST(node.right, node.data, maxValue));
}
public static void main(String[] args)
{
/*
Constructing following tree
4
2 5
1 3 NA 7
*/
BinaryTree binaryTree = new BinaryTree();
binaryTree.create(4);
Node root = binaryTree.search(4);
binaryTree.add(root, 2, BinaryTree.LEFT);
binaryTree.add(root, 5, BinaryTree.RIGHT);
binaryTree.add(binaryTree.search(2), 1, BinaryTree.LEFT);
binaryTree.add(binaryTree.search(2), 3, BinaryTree.RIGHT);
binaryTree.add(binaryTree.search(5), 7, BinaryTree.RIGHT);
System.out.println("Binary Tree in level order is .... ");
binaryTree.printLevelOrder();
IsBstEfficient bTree = new IsBstEfficient();
if(bTree.isBST(root))
{
System.out.println("Given binary tree is a binary search tree");
}
else
{
System.out.println("Given binary tree is not a binary search tree");
}
}
}
References:
http://en.wikipedia.org/wiki/Binary_search_tree
http://cslibrary.stanford.edu/110/BinaryTrees.html
Please write comments if you find any of the above algorithms or codes incorrect, or find better ways to solve the same problem.
Posted by Programming Interview Questions 
Programming Interview Questions 