Friday, February 25, 2011

Java program for Non recursive tree traversal using stack

public void inorderNonRecursive(TreeNode rootnode)
{
Stack stack =new Stack();
Processable info;
TreeNode temp;
temp=rootnode;

while(true)
{
while(temp!=null)
{
stack.push(temp);
temp=temp.left;
}
if(stack.isEmpty())
break;
temp=(TreeNode)stack.pop();
info=(Processable)temp.data;
info.process();
temp=temp.right;

}


}

3 comments:

Unknown said...

Thank you :)

Glad I stumbled on your site, looks very helpful in preparing for interviews.

Quincy said...
This comment has been removed by the author.
Quincy said...

I think the code can be made simpler. Here is my attempt.
public void nonRecursiveTraverse() {
Stack s = new Stack();
s.push(root);
while(!s.isEmpty()) {
Node n = s.pop();
System.out.println(n.value);
if (n.left != null)
s.push(n.left);
if (n.right != null)
s.push(n.right);
}
}