What is Binary Search Tree(BST)? A binary search tree (BST) is a node based binary tree data structure. Must have these 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.
Implementation:
/**
*
*/
package com.bst;
/**
* @author Abhinaw.Tripathi
*
*/
class Node
{
int data;
Node left,right;
public Node(int item)
{
this.data=item;
left=right=null;
}
}
public class BinaryTree
{
/**
*
*/
private Node root;
public BinaryTree()
{
// TODO Auto-generated constructor stub
}
public boolean isBSTUtil(Node node,int min,int max)
{
if(node == null)
return true;
if(node.data < min || node.data> max)
return false;
return (isBSTUtil(node.left, min, node.data-1) && isBSTUtil(node.right, node.data+1, max));
}
public boolean isBST()
{
return isBSTUtil(root, Integer.MIN_VALUE,Integer.MAX_VALUE);
}
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
BinaryTree tree = new BinaryTree();
tree.root = new Node(4);
tree.root.left = new Node(2);
tree.root.right = new Node(5);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(3);
if (tree.isBST())
{
System.out.println("IS BST");
}
else
{
System.out.println("Not a BST");
}
}
}
Time Complexity: O(n)
Auxiliary Space : O(1)
If Function Call Stack size is not valid, otherwise O(n)