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:
Subscribe to: Posts (Atom)