Java Data Structure Implementation : Binary Search Tree

This program demonstrates the Binary Tree implementation in Java. The Insert, Delete, Traversal (Preorder,Inorder,Postorder) Operation has been implemented.

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Binary Tree Implementation in java with Insert/Traversal/Delete Operations.
* @author : Madan Gopal Singh
* @version : 2.0
* @date : 16th March, 2013
*/
public class Tree {
Tree left;
int id;
Tree right;
static Tree prevNode;
static Tree permanentRoot;

public Tree() {
}
public Tree(int id){
left = null;
this.id = id;
right = null;
}
public Tree(Tree left,int id,Tree right){
this.left = left;
this.id =id;
this.right = right;
}
/**
* This method add a new node into the binary tree.
* @param rootNode The Starting node of Tree.
* @param toBeInsertedNodeId The node which you want to insert
* @return Tree.
*/
public static Tree insertNewNodeInTree(Tree rootNode,int toBeInsertedNodeId){
Tree tempRootNode = rootNode;
if(rootNode.left==null && rootNode.right==null){
if(toBeInsertedNodeId<=rootNode.id){
System.out.println("Inserting Left Branch");
rootNode.left = new Tree(toBeInsertedNodeId);
}else{
System.out.println("Inserting Right Branch");
rootNode.right = new Tree(toBeInsertedNodeId);
}
}else{
if(toBeInsertedNodeId<=rootNode.id){
if(rootNode.left==null){
System.out.println("Inserting into Left Subtree");
rootNode.left = new Tree(toBeInsertedNodeId);
}else{
System.out.println("Traversing Left Subtree");
rootNode = insertNewNodeInTree(rootNode.left, toBeInsertedNodeId);
}
}else{
if(rootNode.right==null){
System.out.println("Inserting into Right Subtree");
rootNode.right = new Tree(toBeInsertedNodeId);
}else{
System.out.println("Traversing Right Subtree");
rootNode = insertNewNodeInTree(rootNode.right, toBeInsertedNodeId);
}
}
}
return tempRootNode;
}
/**
* This method performs preorder travarsal of the binary tree.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static Tree treePreOrderTraversal(Tree root){
System.out.print(root.id+" ");
if(root.left==null&&root.right==null){
return root;
}else{
if(root.left!=null){
treePreOrderTraversal(root.left);
}
if(root.right!=null){
treePreOrderTraversal(root.right);
}
}
return root;
}
/**
* This method performs inorder travarsal of the binary tree.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static Tree treePostOrderTraversal(Tree root){
if(root.left==null&&root.right==null){
System.out.print(root.id+" ");
return root;
}else{
if(root.left!=null){
treePostOrderTraversal(root.left);
}
if(root.right!=null){
treePostOrderTraversal(root.right);
}
System.out.print(root.id+" ");
}
return root;
}
/**
* This method performs postorder travarsal of the binary tree.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static Tree treeInOrderTraversal(Tree root){
if(root.left==null&&root.right==null){
System.out.print(root.id+" ");
return root;
}else{
if(root.left!=null){
treeInOrderTraversal(root.left);
}
System.out.print(root.id+" ");
if(root.right!=null){
treeInOrderTraversal(root.right);
}
}
return root;
}
/**
* This method performs removal of node from the binary tree.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static Tree deleteNodeFromTree(Tree root,int nodeIdOfWhichDelete){
if(root == null){
System.out.println("No root found Please try later.");
return null;
}
System.out.println("Callee Id : "+root.id);
if(nodeIdOfWhichDelete!=root.id)
permanentRoot = root;
Tree minimumNode = null;
if(root.id==nodeIdOfWhichDelete){
if(root.left==null && root.right==null){
System.out.println("Deleting Leaf Node");
if(nodeIdOfWhichDelete<permanentRoot.id)
permanentRoot.left=null;
else
permanentRoot.right=null;
return root;
}else{
if(root.left==null){
System.out.println("Looking for node which have one node as child in right sub tree");
System.out.println("Permanent Root ID : "+permanentRoot.id);
System.out.println("Root in right branch");
permanentRoot.left=root.right;
}else{
if(root.right==null){
System.out.println("Looking for node which have one node as child in left sub tree");
System.out.println("Permanent Root ID : "+permanentRoot.id);
System.out.println("Root in left branch");
permanentRoot.right=root.left;
}else{
if(root.right.left!=null){
System.out.println("Looking for node which have exactly two child");
minimumNode = Tree.getMinimumElementFromRightTree(root.right);
System.out.println("Root of Minimum : "+prevNode.id);
System.out.println("Minimum Node in right sub tree : "+minimumNode.id);
root.id = minimumNode.id;
prevNode.left = minimumNode.right;
}else{
System.out.println("Looking for node which have exactly two child");
minimumNode = Tree.getMinimumElementFromRightTree(root.right);
System.out.println("Root of Minimum : "+prevNode.id);
System.out.println("Minimum Node in right sub tree : "+minimumNode.id);
root.id = minimumNode.id;
root.right = minimumNode.right;
}
}
}
}
}else{
if(nodeIdOfWhichDelete<root.id){
System.out.println("Traversing left Subtree");
Tree.deleteNodeFromTree(root.left, nodeIdOfWhichDelete);
}else{
System.out.println("Traversing right Subtree");
Tree.deleteNodeFromTree(root.right, nodeIdOfWhichDelete);
}
}
return permanentRoot;
//System.out.println(Tree.getMinimumElementFromRightTree(root).id);
}

/**
* This method minimum element from left subtree of specified Node.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static Tree getMinimumElementFromRightTree(Tree root){
if(root.left==null){
return root;
}else{
prevNode = root;
return getMinimumElementFromRightTree(root.left);
}
}

/**
* Main Method
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
Tree rootNode = null;
int nodeId = 0,userOperation=0;
String mainMenuString = "";
Scanner sc = new Scanner(System.in);
do{
mainMenuString = "What operation you want to perform?"+
"\n 1. Insert New Node "+
"\n 2. Preorder Traversal"+
"\n 3. Inorder Traversal"+
"\n 4. Postorder Traversal"+
"\n 5. Delete a Node"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(mainMenuString);
userOperation = sc.nextInt();
switch(userOperation){
case 1:
System.out.println("Please enter the Node Id to which you want to insert : ");
nodeId = sc.nextInt();
if(rootNode==null){
rootNode = new Tree(nodeId);
}else{
Tree.insertNewNodeInTree(rootNode, nodeId);
}
break;
case 2:
System.out.println("Preorder traversal sequence : ");
if(rootNode!=null){
Tree.treePreOrderTraversal(rootNode);
}else{
System.out.println("No node to traversal.");
}
break;
case 3:
System.out.println("Inorder traversal sequence : ");
if(rootNode!=null){
Tree.treeInOrderTraversal(rootNode);
}else{
System.out.println("No node to traversal.");
}
break;
case 4:
System.out.println("Postorder traversal sequence : ");
if(rootNode!=null){
Tree.treePostOrderTraversal(rootNode);
}else{
System.out.println("No node to traversal.");
}
break;
case 5:
System.out.println("Please enter the Node Id of which you want to delete : ");
nodeId = sc.nextInt();
Tree.deleteNodeFromTree(rootNode,nodeId);
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
break;
default:
System.out.println("Invalid Operation!! Please try again");
}
}while(userOperation!=-1);
}
}

Any suggestion is invited if any.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s