2. IMPLEMENTATION OF BINARY SEARCH TREE
AIM:
To write a java program
for implementing Binary Search Tree.
ALGORITHM:
1. Read
the search element from the user
2. Compare,
the search element with the value of root node in the tree.
3. If
both are matching, then display "Given node found!!!" and terminate
the function
4. If
both are not matching, then check whether search element is smaller or larger
than that node value.
5. If
search element is smaller, then continue the search process in left subtree.
6. If
search element is larger, then continue the search process in right subtree.
7. Repeat
the same until we found exact element or we completed with a leaf node
8. If
we reach to the node with search value, then display "Element is
found" and terminate the function.
9. If
we reach to a leaf node and it is also not matching, then display "Element
not found" and terminate the function.
PROGRAM :
public class BinarySearchTree
{
public static Node
root;
public BinarySearchTree()
{
this.root = null;
}
public boolean find(int id)
{
Node current = root;
while(current!=null)
{
if(current.data==id)
{
return true;
}
else if(current.data>id)
{
current = current.left;
}
Else
{
current = current.right;
}
}
return false;
}
public boolean delete(int id)
{
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id)
{
parent = current;
if(current.data>id)
{
isLeftChild = true;
current = current.left;
}
Else
{
isLeftChild = false;
current = current.right;
}
if(current ==null)
{
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null)
{
if(current==root)
{
root = null;
}
if(isLeftChild ==true)
{
parent.left = null;
}
Else
{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null)
{
if(current==root)
{
root = current.left;
}
else if(isLeftChild)
{
parent.left = current.left;
}
Else
{
parent.right = current.left;
}
}
else if(current.left==null)
{
if(current==root)
{
root = current.right;
}
else if(isLeftChild)
{
parent.left = current.right;
}
Else
{
parent.right = current.right;
}
}
else if(current.left!=null && current.right!=null)
{
//now we have found the minimum element in the right sub
tree
Node successor
= getSuccessor(current);
if(current==root)
{
root = successor;
}
else if(isLeftChild)
{
parent.left = successor;
}
Else
{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
public Node getSuccessor(Node deleleNode)
{
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null)
{
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have
left child for sure
// if it does have the right child, add it to the left of
successorParent.
// successsorParent
if(successsor!=deleleNode.right)
{
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id)
{
Node newNode = new Node(id);
if(root==null)
{
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true)
{
parent = current;
if(id<current.data)
{
current = current.left;
if(current==null)
{
parent.left = newNode;
return;
}
}
Else
{
current = current.right;
if(current==null)
{
parent.right = newNode;
return;
}
}
}
}
public void display(Node root)
{
if(root!=null)
{
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[])
{
BinarySearchTree b = new BinarySearchTree();
b.insert(3);b.insert(8);
b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
b.insert(20);b.insert(25);b.insert(15);b.insert(16);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4
exists : " + b.find(4));
System.out.println("Delete Node with no children (2) :
" + b.delete(2));
b.display(root);
System.out.println("\n Delete Node with one child (4) :
" + b.delete(4));
b.display(root);
System.out.println("\n Delete Node with Two children
(10) : " + b.delete(10));
b.display(root);
}
}
class Node
{
int data;
Node left;
Node right;
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}