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
No comments:
Post a Comment