Saturday 17 April 2021

Using Iteration Implement Binary Search Tree

 Implementing binary search tree Using Iteration.
Depth First Search(DFS) :-

  • Inorder Traversal(LNR)=> Left Node Right
  • Preorder Traversal(NLR)
  • Postorder Traversal(LRN)
=================================================



package com.java.recursion;
import java.util.Scanner;
public class BSTWithIterationMethod {
public static Node root;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println(
"1. Create \t2. InOrder \t3. preOrder \t4. postOrder \t5. preOrderSecondWay \t6. postOrderTwoStack");
int operation = sc.nextInt();
switch (operation) {
case 1:
System.out.println("How many node you want to create");
int noOfNode = sc.nextInt();
for (int i = 0; i < noOfNode; i++) {
System.out.println("Enter node value");
int data = sc.nextInt();
create(data);
}
break;
case 2:
InOrder(root);
System.out.println();
break;
case 3:
preOrder(root);
System.out.println();
break;
case 4:
postOrder(root);
System.out.println();
break;
case 5:
preOrderSecondWay(root);
System.out.println();
break;
case 6:
postOrderTwoStack(root);
System.out.println();
break;
}
}
}
private static void create(int data) {
Node temp = new Node(data);
if (root == null) {
root = temp;
return;
}
Node copy = root;
Node CR = root;
while (copy != null) {
CR = copy;
if (copy.data > data) {
copy = copy.left;
} else if (copy.data < data) {
copy = copy.right;
}
}
if (CR.data > data) {
CR.left = temp;
} else if (CR.data < data) {
CR.right = temp;
}
}
private static void InOrder(Node root) {
if (root == null) {
return;
}
Node[] stack = new Node[20];
int top = -1;
Node copy = root;
while (copy != null) {
stack[++top] = copy;
copy = copy.left;
}
while (top > -1) {
Node temp = stack[top--];
System.out.print(temp.data + " ");
if (temp.right != null) {
Node temp2 = temp.right;
while (temp2 != null) {
stack[++top] = temp2;
temp2 = temp2.left;
}
}
}
}
private static void preOrder(Node root) {
if (root == null) {
return;
}
Node[] stack = new Node[20];
int top = -1;
while (root != null) {
System.out.print(root.data + " ");
stack[++top] = root;
root = root.left;
}
while (top > -1) {
Node copy = stack[top--];
if (copy.right != null) {
Node temp = copy.right;
while (temp != null) {
System.out.print(temp.data + " ");
stack[++top] = temp;
temp = temp.left;
}
}
}
}
private static void postOrder(Node root) {
if (root == null) {
return;
}
Node[] stack = new Node[20];
int top = -1;
Node copy = root;
while (copy != null) {
if (copy.right != null) {
stack[++top] = copy.right;
}
stack[++top] = copy;
copy = copy.left;
}
while (top > -1) {
Node pop = stack[top--];
if (top != -1 && pop.right != null && stack[top] == pop.right) {
Node temp = stack[top--];
stack[++top] = pop;
while (temp != null) {
if (temp.right != null) {
stack[++top] = temp.right;
}
stack[++top] = temp;
temp = temp.left;
}
} else {
System.out.print(pop.data + " ");
}
}
}
private static void preOrderSecondWay(Node root) {
if(root==null){
return;
}

 Node[] stack= new Node[10];
int top=-1;
stack[++top]=root;
while(top>-1){
Node copy=stack[top--];
System.out.print(copy.data+" ");
if(copy.right!=null){
stack[++top]=copy.right;
}
if(copy.left!=null){
stack[++top]=copy.left;
}

 }

}
private static void postOrderTwoStack(Node root) {
if(root==null){
return;
}

 Node[] stack=new Node[10];
Node[] stack2=new Node[10];
int top=-1;
int top2=-1;

 stack[++top]=root;

 while(top>-1){
Node copy=stack[top--];
if(copy.left!=null){
stack[++top]=copy.left;
}
if(copy.right!=null){
stack[++top]=copy.right;
}
stack2[++top2]=copy;
}

 while(top2>-1){
System.out.print(stack2[top2--].data+" ");
}
}
}


Posted by at No comments:

Left view and right view of Binary search tree Using recursion

 We have implemented left view and right view of BST using recursion.

============Tree Structure like below============

                                            20
                                         /        \
                                      10          30
                                         \         /     \
                                        15     25      35
                                                    \
                                                     26
                                                         \
                                                          27

Left View :- 20  10  15  26  27
Right View :- 20  30  35  26  27

=================================================

package com.java.recursion;

import java.util.Scanner;

public class LeftViewOfBST {
public static Node root;
public static int count = 0;
public static int maxValue=0;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {

System.out.println("1. Create \t2. InOrder \t3. leftviewOfBST \t4. rightViewOfTree");

int operation = sc.nextInt();
switch (operation) {
case 1:
System.out.println("How many node you want to create");
int noOfNode = sc.nextInt();
for (int i = 0; i < noOfNode; i++) {
System.out.println("Enter node value");
int data = sc.nextInt();
create(data);
}
break;
case 2:
InOrder(root);
System.out.println();
break;
case 3:
leftviewOfBST(root);
System.out.println();
break;
case 4:
rightViewOfTree(root,0);
System.out.println();
break;
}
}

}


private static void create(int data) {
Node temp = new Node(data);
if (root == null) {
root = temp;
return;
}

Node copy = root;
Node CR = root;
while (copy != null) {
CR = copy;
if (copy.data > data) {
copy = copy.left;
} else if (copy.data < data) {
copy = copy.right;
}
}

if (CR.data > data) {
CR.left = temp;
} else if (CR.data < data) {
CR.right = temp;
}

}

private static void InOrder(Node root) {
if (root == null) {
return;
}
InOrder(root.left);
System.out.print(root.data + " ");
InOrder(root.right);
}

private static void leftviewOfBST(Node root) {
if (root == null) {
return;
}
int height = height(root);

for (int i = 1; i <= height; i++) {
count = 0;
printLeftView(root, i);
}

}

private static void printLeftView(Node root, int level) {
if (root == null) {
return;
}
if (level == 1 && count == 0) {
System.out.println(root.data + " ");
count++;
return;
}
printLeftView(root.left, level - 1);
printLeftView(root.right, level - 1);

}

private static int height(Node root) {
if (root == null) {
return 0;
}
return max(height(root.left), height(root.right)) + 1;
}

private static int max(int a, int b) {
return a > b ? a : b;
}
private static void rightViewOfTree(Node root,int level) {
if(root==null){
return;
}
if(level>=maxValue){
System.out.print(root.data+" ");
maxValue++;
}
rightViewOfTree(root.right,level+1);
rightViewOfTree(root.left,level+1);
}
}


========== Output of the program ============


1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
1
How many node you want to create
8
Enter node value
20
Enter node value
10
Enter node value
30
Enter node value
15
Enter node value
25
Enter node value
35
Enter node value
26
Enter node value
27
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
2
10 15 20 25 26 27 30 35 
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
3
20 
10 
15 
26 
27 

1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree
4
20 30 35 26 27 
1. Create 2. InOrder 3. leftviewOfBST 4. rightViewOfTree

Posted by at No comments:

Reversal Of Binary Search Tree Using Stack and Queue and Recursion

 Reversal Of Binary Search Tree Using Stack and Queue and Recursion :-


Suppose we have tree like :-

                   20 => root
                /       \
            10         30
           /    \        /   \
         5     15   25   35


we have to print data in level order like :-   20  10  30  5  15  25  35
And reversal of Tree will be :-  35  25 15  5  30  10  20
Reversal of Level Order will be :-  5  15  25  35  10  30  20


For that we have to write program like below :-


package com.java.recursion;

import java.util.Scanner;

public class LeverOrderWithoutRecursion {

public static Node root;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("1. Create \t2. levelOrderusingqueue \t3. levelorderUsingStack \t4. reverseTreeUsingQueue \t5. reverseTreeUsingStack \t6. reverseLevelOrderTraversalUsingRecursion \t7. reverseLevelOrderUsingQueue \t8. reverseLevelOrderUsingStack");
int operation=sc.nextInt();
switch(operation){
case 1:
System.out.println("How many node you want to create");
int noOfNode=sc.nextInt();
for(int i=0;i<noOfNode;i++){
System.out.println("Enter node value");
int data=sc.nextInt();
create(data);
}
break;
case 2:
lebelOrderUsingQueue(root);
break;
case 3:
lebelOrderUsingStack(root);
break;
case 4:
reverseTreeUsingQueue(root);
break;
case 5:
reverseTreeUsingStack(root);
break;
case 6:
reverseLevelOrderTraversalUsingRecursion(root);
break;
case 7:
reverseLevelOrderUsingQueue(root);
break;
case 8:
reverseLevelOrderUsingStack(root);
break;
}
}

}


private static void create(int data) {
Node temp=new Node(data);
if(root==null){
root=temp;
return;
}
Node copy=root;
Node CR=root;
while(copy!=null){
CR=copy;
if(copy.data>data){
copy=copy.left;
}else if(copy.data<data){
copy=copy.right;
}
}
if(CR.data>data){
CR.left=temp;
}else if(CR.data<data){
CR.right=temp;
}
}



private static void lebelOrderUsingQueue(Node root) {
Node[] queue=new Node[7];
int front=-1,rear=-1;
if(root==null){
System.out.println("Empty BST");
return;
}
queue[++rear]=root;
++front;
while(front<=rear){
Node copy=queue[front++];
System.out.print(copy.data+" ");
if(copy.left!=null){
queue[++rear]=copy.left;
}
if(copy.right!=null){
queue[++rear]=copy.right;
}
}
System.out.println();
}
private static void lebelOrderUsingStack(Node root) {
Node[] stack =new Node[7];
int top=-1,top1=-1;
if(root==null){
System.out.println("Empty BST");
return;
}
stack[++top]=root;
++top1;
while(top>=top1){
Node copy=stack[top1++];
System.out.print(copy.data+" ");
if(copy.left!=null){
stack[++top]=copy.left;
}
if(copy.right!=null){
stack[++top]=copy.right;
}
}
System.out.println();
}



private static void reverseTreeUsingQueue(Node root) {
Node[] queue=new Node[7];
int front=-1,rear=-1;
if(root==null){
System.out.println("Empty BST");
return;
}
queue[++rear]=root;
++front;
while(front<=rear){
Node copy=queue[front++];
System.out.print(copy.data+" ");
if(copy.left!=null){
queue[++rear]=copy.left;
}
if(copy.right!=null){
queue[++rear]=copy.right;
}
}
System.out.println();
while(front>0){
Node copy=queue[--front];
System.out.print(copy.data+" ");
}
System.out.println();
}
private static void reverseTreeUsingStack(Node root) {
Node[] stack =new Node[7];
int top=-1,top1=-1;
if(root==null){
System.out.println("Empty BST");
return;
}
stack[++top]=root;
++top1;
while(top>=top1){
Node copy=stack[top1++];
System.out.print(copy.data+" ");
if(copy.left!=null){
stack[++top]=copy.left;
}
if(copy.right!=null){
stack[++top]=copy.right;
}
}
System.out.println();
while(top>-1){
Node copy=stack[top--];
System.out.print(copy.data+" ");
}
System.out.println();
}
private static void reverseLevelOrderTraversalUsingRecursion(Node root) {
if(root==null){
return;
}
int height=height(root);
for(int i=height;i>=0;i--){
levelOrderTraversal(root,i);
}
System.out.println();
}



private static void levelOrderTraversal(Node root, int level) {
if(root==null){
return;
}
if(level==1){
System.out.print(root.data+" ");
}
levelOrderTraversal(root.left,level-1);
levelOrderTraversal(root.right,level-1);
}



private static int height(Node root) {
if(root==null){
return 0;
}
return max(height(root.left),height(root.right))+1;
}



private static int max(int a, int b) {
return a>b?a:b;
}

private static void reverseLevelOrderUsingQueue(Node root) {
Node[] queue=new Node[7];
int front=-1,rear=-1;
if(root==null){
System.out.println("Empty BST");
return;
}
queue[++rear]=root;
++front;
while(front<=rear){
Node copy=queue[front++];
System.out.print(copy.data+" ");
if(copy.right!=null){
queue[++rear]=copy.right;
}
if(copy.left!=null){
queue[++rear]=copy.left;
}
}
System.out.println();
while(front>0){
Node copy=queue[--front];
System.out.print(copy.data+" ");
}
System.out.println();
}



private static void reverseLevelOrderUsingStack(Node root) {
Node[] stack =new Node[7];
int top=-1,top1=-1;
if(root==null){
System.out.println("Empty BST");
return;
}
stack[++top]=root;
++top1;
while(top>=top1){
Node copy=stack[top1++];
System.out.print(copy.data+" ");
if(copy.right!=null){
stack[++top]=copy.right;
}
if(copy.left!=null){
stack[++top]=copy.left;
}
}
System.out.println();
while(top>-1){
Node copy=stack[top--];
System.out.print(copy.data+" ");
}
System.out.println();
}


}





======== OUTPUT will be display Like Below   ========


1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
1
How many node you want to create
7
Enter node value
20
Enter node value
10
Enter node value
30
Enter node value
5
Enter node value
15
Enter node value
25
Enter node value
35

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
2

20 10 30 5 15 25 35 


1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
3

20 10 30 5 15 25 35 

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
4

20 10 30 5 15 25 35 
35 25 15 5 30 10 20 

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
5

20 10 30 5 15 25 35 
35 25 15 5 30 10 20 

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
6

5 15 25 35 10 30 20 

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
7

20 30 10 35 25 15 5 
5 15 25 35 10 30 20 

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack
8

20 30 10 35 25 15 5 
5 15 25 35 10 30 20 

1. Create 2. levelOrderusingqueue 3. levelorderUsingStack 4. reverseTreeUsingQueue 5. reverseTreeUsingStack 6. reverseLevelOrderTraversalUsingRecursion 7. reverseLevelOrderUsingQueue 8. reverseLevelOrderUsingStack

Posted by at No comments:

Monday 12 April 2021

Binary Search tree traversal using recursion

  Binary search traversal we can do with two ways.

1.) Breadth First Traversal(BFS) :-  we use level order traversal for it.

2.) Depth Order Traversal(DFS) :- we can implement DFS with three ways.

  • Preorder Traversal :- it will print as first ROOT Node, then LEFT, after that RIGHT(NLR).
  • Inorder Traversal :- it will print as first LEFT tree, then Root node, after that RIGHT(LNR).
  • Postorder Traversal :- it will print as first LEFT tree, then RIGHT tree, after that Root node(LRN).

package com.java.recursion;

public class Node {
int data;
Node left,right;
public Node(int data){
this.data=data;
left=right=null;
}

public String toString(){
return hashCode()+"";
}
}


Implementation class for BFS and DFS traversal using recursion.

package com.java.recursion;

import java.util.Scanner;

public class TraversalBST {

public static Node root;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("1. Create \t2. Preorder \t3. Inorder \t4. Postorder \t5. lebelorder");
int operation=sc.nextInt();
switch(operation){
case 1:
System.out.println("How many node you want to create");
int noOfNode=sc.nextInt();
for(int i=0;i<noOfNode;i++){
System.out.println("Enter node value");
int data=sc.nextInt();
create(data);
}
break;
case 2:
preOrder(root);
break;
case 3:
inOrder(root);
break;
case 4:
postOrder(root);
break;
case 5:
lebelOrder(root);
break;
}
}

}
private static void create(int data) {
Node temp=new Node(data);
if(root==null){
root=temp;
return;
}
Node copy=root;
Node CR=root;
while(copy!=null){
CR=copy;
if(copy.data>data){
copy=copy.left;
}else if(copy.data<data){
copy=copy.right;
}
}
if(CR.data>data){
CR.left=temp;
}else if(CR.data<data){
CR.right=temp;
}
}
private static void preOrder(Node root) {
if(root==null){
return;
}
System.out.print(root.data+" , ");
preOrder(root.left);
preOrder(root.right);
}
private static void inOrder(Node root) {
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.data+" , ");
inOrder(root.right);
}
private static void postOrder(Node root) {
if(root==null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+" , ");
}
private static void lebelOrder(Node root) {
// TODO Auto-generated method stub
int h=height(root);
System.out.println("Height is : "+h);
for(int i=1;i<=h;i++){
lebelOrderDisplay(root,i);
}
}
private static void lebelOrderDisplay(Node root, int level) {
if(root==null){
return;
}
if(level==1){
System.out.print(root.data+" , ");
}
if(level>=1){
lebelOrderDisplay(root.left,level-1);
lebelOrderDisplay(root.right,level-1);
}
}
private static int height(Node root){
if(root==null){
return 0;
}
int leftHeight=height(root.left);
int rightHeight=height(root.right);
if(leftHeight<rightHeight){
return leftHeight+1;
}else{
return rightHeight+1;
}
}

}


Posted by at No comments:

Sunday 28 March 2021

Circular Queue

Queue is first in first out (FIFO) data structure.we will implement queue data structure with one front and one rear end and one queue of array.
Initially front and rear end value will be [-1].
FRONT :- when we delete data from queue then front will increment.
REAR :- when we add element in queue then rear will increment.




package com.java.cqds;

import java.util.Scanner;

public class CircularQeue {
public static int[] queue=new int[5];
public static int front=-1,rear=-1;

public static void main(String[] args) {
System.out.println("Jai shree ram !!!");
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("1. Create \t2. Display \t3. Delete");
int operation = sc.nextInt();
switch (operation) {

case 1:
System.out.println("Enter the queue value to create");
int data = sc.nextInt();
create(data);
break;
case 2:
display();
break;
case 3:
delete();
break;
default:
System.out.println("Operation not found !!!");
break;
}
}


}


Below method is used to create the queue.

private static void create(int data) {
if((front==0 && rear==queue.length-1)||(front==rear+1)){
System.out.println("Quee is full");
return;
}else{
if(front==-1 && rear==-1){
rear++;
front++;
}else{
rear++;
}
if(rear==queue.length){
rear=0;
}
queue[rear]=data;
}
}


Below method is used to display the queue.


private static void display() {
if(front==-1 && rear==-1){
System.out.println("Empty circular queue");
return;
}else{
int front1=front;
int rear1=rear;
if(front1>rear1){
while(front1<=queue.length-1){
System.out.println(queue[front1++]+" ");
}
front1=0;
while(front1<=rear1){
System.out.println(queue[front++]+" ");
}
}else{
while(front1<=rear1){
System.out.println(queue[front++]+" ");
}
}
}
}


Below method is used to delete the queue.


private static void delete() {
if(front==-1 && rear==-1){
System.out.println("Empty Circular linked list");
return;
}else{
System.out.println(queue[front]+"");
if(front==queue.length-1){
front=0;
}else{
front++;
}
if((front==rear+1)||(front==0 && rear==queue.length-1)){
rear=front=-1;
}
}
}



}

Posted by at No comments:

Regular Queue

 Queue is first in first out (FIFO) data structure.we will implement queue data structure with one front and one rear end and one queue of array.
Initially front and rear end value will be [-1].
FRONT :- when we delete data from queue then front will increment.
REAR :- when we add element in queue then rear will increment.



package com.java.qds;

import java.util.Scanner;

public class RegularQueue {

public static int front = -1, rear = -1;
public static int[] queue = new int[5];

public static void main(String[] args) {

System.out.println("Jai shree ram !!!");
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("1. Create \t2. Display \t3. Delete");
int operation = sc.nextInt();
switch (operation) {

case 1:
System.out.println("Enter the queue value to create");
int data = sc.nextInt();
create(data);
break;
case 2:
display();
break;
case 3:
delete();
break;
default:
System.out.println("Operation not found !!!");
break;
}
}

}

Below method is used to create the queue.


public static void create(int data) {
if(rear==queue.length-1){
System.out.println("Queue is overflow !!!");
return;
}
if(front==-1 && rear==-1){
rear++;
front++;
}else{
rear++;
}
queue[rear]=data;

}

Below method is used to display element in queue.


public static void display() {
if((front==-1 && rear==-1) || front==rear+1){
System.out.println("Empty Queue");
return;
}
for(int i=front;i<=rear;i++){
System.out.println(queue[i]);
}

/*///OR
int j=front;
while(j<=rear){
System.out.println(queue[j++]);
}*/
}

Below Method is uses to delete the element from queue.


public static void delete() {

if((front==-1 && rear==-1) || front==rear+1){
System.out.println("Empty queue");
return;
}
System.out.println("Deleted element is "+queue[front++]);
}

}


Posted by at No comments:

Saturday 27 March 2021

Binary Search Tree using java

 Create a Node Using java for binary search tree.we will use this node in creating node in binary search tree .Traversing Inorder ,preorder and postorder traversal. It is also used in searching a node or deleting a node.

package com.java.bstds;
public class Node {
int data;
Node left,right;

public Node(int data){
this.data=data;
}
public String toString(){
return hashCode()+"";
}
}


To Implement the logic I am writing following code inside main method so that we can used all services.


package com.java.bstds;

import java.util.Scanner;

public class BST {

public static Node root;

// For Searching element we used below reference
public static Node avail, parent;

public static void main(String[] args) {
System.out.println("Jai shree Ganesh !!!");

Scanner sc = new Scanner(System.in);
while (true) {
System.out.println();
System.out.println(
"1. Create \t2. Inorder Traversal \t3. Preorder Travelsal \t4. Postorder Traversal \t5. Search Element \t6. Delete");
int operation = sc.nextInt();
switch (operation) {
case 1:
System.out.println("How many number of node you want to create");
int noOfNode = sc.nextInt();
for (int i = 0; i < noOfNode; i++) {
System.out.println("Enter the node value to create");
int data = sc.nextInt();
create(data);
}
break;
case 2:
inOrderTraversal();
break;
case 3:
preOrderTraversal();
break;
case 4:
postOrderTraversal();
break;
case 5:
System.out.println("Enter element which you want to search");
int ele = sc.nextInt();
Node avl = search(ele);
if (avl != null) {
System.out.println("Element is " + avail.data);
if (parent != null) {
System.out.println("which parent is " + parent.data);
}
} else {
System.out.println("Element Not Found");
}
break;
case 6:
System.out.println("Enter node value which you want to delete");
int value = sc.nextInt();
delete(value);
break;
default:
System.out.println("Not found any index");
break;

}
}

}
}


To create a node and add element greater than root node is right side of the root and element less than the root will store inside left side of the root.To implement that logic we have gone through below case.


public static void create(int data) {
Node temp = new Node(data);
if (root == null) {
root = temp;
return;
} else {
Node copyRoot = root;
Node newNode = null;
while (copyRoot != null) {
newNode = copyRoot;
if (copyRoot.data > data) {
copyRoot = copyRoot.left;
} else if (copyRoot.data < data) {
copyRoot = copyRoot.right;
} else {
copyRoot = null;
}
}

if (newNode.data > data) {
newNode.left = temp;
} else if (newNode.data < data) {
newNode.right = temp;
} else if (newNode.data == data) {
temp = null;
}

}
}


To implement the Traversal in tree we have three ways to traverse the tree .
1. Inorder Traversal(LNR)
2. Preorder Traversal(NLR)
3. Postorder Traversal(LRN)
So let us see one by one.
1. Inorder traversal : First it will traverse left node then root and then right node.This rule is applicable for all node.


public static void inOrderTraversal() {
if (root == null) {
System.out.println("Empty BST ");
return;
} else {
Node copyRoot = root;
Node[] stack = new Node[20];
int top = -1;

try {
while (true) {
while (copyRoot != null) {
stack[++top] = copyRoot;
copyRoot = copyRoot.left;
}
copyRoot = stack[top--];
if (copyRoot.right != null) {
System.out.print("  " + copyRoot.data + " ");
copyRoot = copyRoot.right;
} else {
System.out.print(" " + copyRoot.data + " ");
copyRoot = null;
}
}

} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}


2. Preorder Traversal(NLR) : first it will traverse root then left and then right and it is applicable of all node.


public static void preOrderTraversal() {
if (root == null) {
System.out.println("Empty BST");
return;
} else {
Node copyRoot = root;
Node[] stack = new Node[20];
int top = -1;
try {
while (true) {
while (copyRoot != null) {
System.out.print(copyRoot.data + " ");
stack[++top] = copyRoot;
copyRoot = copyRoot.left;
}
copyRoot = stack[top--];
if (copyRoot.right != null) {
copyRoot = copyRoot.right;
} else {
copyRoot = null;
}
}

} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}

3.Postorder Traversal (LRN):- In this traversal we have first gone through left node the right node and then root node. and it is applicable for all node. Root node will be printed only when its is traverse at 3rd times.

public static void postOrderTraversal() {

if (root == null) {
System.out.println("Empty BST");
return;
} else {
Node copyRoot = root;
Node[] stack = new Node[20];
int top = -1;

try {
while (true) {
while (copyRoot != null) {
if (copyRoot.right != null) {
stack[++top] = copyRoot.right;
}
stack[++top] = copyRoot;
copyRoot = copyRoot.left;
}

copyRoot = stack[top--];
if (top != -1 && copyRoot.right != null && stack[top] == copyRoot.right) {
stack[top] = copyRoot;
copyRoot = copyRoot.right;
} else {
System.out.print(copyRoot.data + " ");
copyRoot = null;
}

}
} catch (ArrayIndexOutOfBoundsException e) {
e.printStackTrace();
}

}
}


To search a particular element from Binary search tree we are using below method.to search a element basically we want to find the node of element and its parent of the element. this search will also used in deleting a node from BST.


public static Node search(int data) {

avail = null;
if (root == null) {
System.out.println("Empty BST");
return null;
} else {
if (root.data == data) {
avail = root;
parent = null;
return avail;
}

Node copyRoot = root, findTree = null;
if (root.data > data) {
findTree = root.left;
} else {
findTree = root.right;
}

while (findTree != null) {
if (findTree.data == data) {
avail = findTree;
parent = copyRoot;
break;
}
copyRoot = findTree;
if (findTree.data > data) {
findTree = findTree.left;
} else {
findTree = findTree.right;
}
}

}

return avail;

}


To delete a node from BST , we have three way to delete a node.
1. If node have not left and right sub tree.(nought method)
2. If node have only left or right sub tree .(crooked method)
3. if node have both left and right sub tree.(hedge method)

public static void delete(int data) {
if (root == null) {
System.out.println("Empty BST");
return;
}
Node avail = search(data);
if (root == avail && root.left == null && root.right == null) {
root = null;
}

if (avail.left == null && avail.right == null) {
nought(avail);
}

if (avail.left != null && avail.right == null) {
crooked(avail);
}
if (avail.right != null && avail.left == null) {
crooked(avail);
}
if(avail.left!=null && avail.right!=null){
hedge(avail);
}
}


1.) To delete a node which haven't left and right node we called nought method.


public static void nought(Node avail) {
// if(parent==null) or if(root==avail)
if (root == avail) {
root = null;
return;
}
if (parent.left == avail) {
parent.left = null;
} else {
parent.right = null;
}
}



2.) If node have only left or right subtree then we will call crooked method.


public static void crooked(Node avail) {
Node copy = null;

if (avail.left != null) {
copy = avail.left;
} else {
copy = avail.right;
}

if (root == avail) {
root=copy;
return;
}
if(parent.left==avail){
parent.left=copy;
}else{
parent.right=copy;
}

}

3.) If node have both left and right tree then we will call hedge method.


public static void hedge(Node avail){
Node copy=avail.right;
Node q=null;
while(copy!=null){
q=copy;
copy=copy.left;
}
Node avail1=avail,parent1=parent;
Node avail2=search(q.data);
if(avail2.right!=null && avail2.left==null){
crooked(avail2);
}else{
nought(avail2);
}
if(parent1==null){
avail2.right=avail1.right;
avail2.left=avail1.left;
root=avail2;
}else{
if(parent1.right==avail1){
parent1.right=avail2;
}else{
parent1.left=avail2;
}
avail2.right=avail1.right;
avail2.left=avail1.left;
}
}








Posted by at No comments:
Subscribe to: Posts (Atom)