- All the values of nodes in the left sub-tree are less than the value in the root node.
- All the values of nodes in the right sub-tree are greater than the root node.
- The left and right sub-trees are also binary search trees
- There mustn't be any duplicate node.
A node implementation
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int val){
value = val;
left = null;
right = null;
}
public TreeNode(){
value = 0;
left = null;
right = null;
}
public void setLeft(TreeNode node){
left=node;
}
public void setRight(TreeNode node){
right=node;
}
public void setValue(int val){
value = val;
}
public int getValue(){
return value;
}
public TreeNode getLeft(){
return left;
}
public TreeNode getRight(){
return right;
}
}
set methods and get methods are implemented because they are helpful to implement binary search tree using class "TreeNode".
Here's the implementation for Binary Search Tree using "TreeNode" class
public class BST {
private TreeNode root;
public BST(){
root = null;
}
/*method to determine whether BST is empty or not*/
public boolean isEmpty(){
return root==null;
}
/*method to insert a node to BST*/
public void insert(int data){
root=insert(root,data);
}
private TreeNode insert(TreeNode node,int data){
if(node==null){
node = new TreeNode(data);
}
else{
if(data<node.getValue())
node.left=insert(node.left,data);
else
node.right=insert(node.right,data);
}
return node;
}
/*method to delete a node from BST*/
public void delete(int val){
if(isEmpty()){
System.out.println("Tree Empty");
}
else if(!search(val))
System.out.println("Sorry "+ val +" is not present");
else{
root=delete(root,val);
System.out.println(val+ " deleted from the tree");
}
}
private TreeNode delete(TreeNode node,int val){
TreeNode n1,n2,k;
if(root.getValue()==val){
TreeNode lt=root.getLeft();
TreeNode rt=root.getRight();
if(lt==null&&rt==null)
return null;
else if(lt==null)
return rt;
else if (rt==null)
return lt;
else{
n1=rt;
n2=rt;
while(n2.getLeft()!=null)
n2=n2.getLeft();
n2.setLeft(lt);
return n1;
}
}
if(val<root.getValue()){
k=delete(root.getLeft(),val);
root.setLeft(k);
}
else{
k=delete(root.getRight(),val);
root.setRight(k);
}
return root;
}
/*method to count number of nodes of BST*/
public int countNodes(){
return countNodes(root);
}
private int countNodes(TreeNode node){
if(node==null)
return 0;
else{
int count=1;
count+=countNodes(node.getLeft());
count+=countNodes(node.getRight());
return count;
}
}
/*method to search element of BST*/
public boolean search(int val){
return search(root,val);
}
private boolean search(TreeNode node,int val){
boolean found=false;
while(node!=null && !found){
if(val<node.getValue())
node=node.getLeft();
else if (val>node.getValue())
node=node.getRight();
else{
found=true;
break;
}
found=search(node,val);
}
return found;
}
}
In this implementation insert, delete, search, methods are also implemented to insert, delete, search data in BST. This BST is implemented only for integer data but remember we can implement Binary Search tree as compatible with any data type using java generics.
