Tree traversals without recursion

package treetravernonrecur;
import java.util.*;
class node
{
node left;
node right;
int data;
int visited;
public node(int val,int visit)
{
data=val;
visited=visit;
}
}

public class treetravernonrecur
{ static void preorder(node root)
{
Stack<node> st=new Stack<node>();
node temp;
if(root!=null)
st.push(root);
while(!st.isEmpty())
{ temp=st.pop();
System.out.println(temp.data);
if(temp.right!=null)
st.push(temp.right);
if(temp.left!=null)
st.push(temp.left);

}

}

static void inorder(node root)
{
Stack<node> st=new Stack<node>();
node temp;
if(root!=null)
st.push(root);
while(!st.isEmpty())
{ temp=st.peek();
if(temp.left!=null && temp.left.visited==0)
st.push(temp.left);
else
{temp=st.pop();
System.out.println(temp.data);
temp.visited=1;
if(temp.right!=null)
st.push(temp.right);

}

}

}

static void postorder(node root)
{
Stack<node> st=new Stack<node>();
node temp;
if(root!=null)
st.push(root);
while(!st.isEmpty())
{ temp=st.peek();
if(temp.left!=null && temp.left.visited==0)
st.push(temp.left);
else if (temp.right!=null && temp.right.visited==0)
st.push(temp.right);
else
{temp=st.pop();
System.out.println(temp.data);
temp.visited=1;

}

}

}

public static void main(String args[])
{
node a=new node(1,0);
node b=new node(2,0);
node c=new node(3,0);
node d=new node(4,0);
node e=new node(5,0);
node f=new node(6,0);
node g=new node(7,0);
node h=new node(8,0)
a.left=b;
a.right=c;
b.left=d;
b.right=e;
c.left=f;
c.right=g;
preorder(a);
inorder(a);
postorder(a)

}
}

Leave a Reply

Your email address will not be published. Required fields are marked *