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+" ");
}
}
}