Home » Algorithms

Non Recursive Tree Traversal Algorithm

In this article, we will learn about the non recursive algorithm of tree traversals like algorithm for pre-order, post-order and in-order.
Submitted by Prerana Jain, on July 26, 2018

1) Algorithm for Postorder

In this traversal first, traverse the leftmost subtree at the external node then visit the root node and lastly traverse the right subtree starting at the left external node.

POSTORD(INFO, LEFT, RIGHT, ROOT)
Step-1 [Push NULL onto STACK and initialize PTR]
   Set TOP=1, STACK[1]=NULL and PTR=ROOT.

Step-2 [Push left-most path onto STACK] repeat step 3 to 5 while PTR not equal NULL.

Step-3 set TOP=TOP+1 and STACK[TOP]=PTR. [Pushes PTR on STACK].

Step-4 if RIGHT[PTR] not equal NULL then [push on STACK.]
   Set TOP=TOP+1 and STACK[TOP]= RIGHT[PTR]
  [End of if structure]

Step-5 set PTR = LEFT[PTR].[Update pointer PTR]
    [End of step 2 loop].

Step-6 set PTR= STACK[TOP] and TOP=TOP-1.
  [Pops node from STACK].

Step-7 Repeat while PTR>0;
  Apply PROCESS TO INFO[PTR].
Set PTR= STACK[TOP] and TOP= TOP-1.
[Pops node from STACK]
[End of loop]

Step-8 if PTR<0 then:
   Set PTR= -PTR
Go to step 2
[End of if structure]

Step-9 Exit.

2) Algorithm for Inorder

In this traversal first traverse, the root node then traverses the left subtree of the external node and lastly traverse the right subtree of the external node.

INORD( INFO, LEFT, RIGHT, ROOT)
Step-1 [Push NULL onto STACK and initialize PTR;]
    Set TOP=1 STACK[1]= NULL and PTR=ROOT.

Step-2 Repeat while PTR not equal NULL[Pushes left most path onto STACK].
a)	Set TOP=TOP+1 and STACK[TOP]=PTR [saves node]
b)	Set PTR=LEFT[PTR] [updates PTR]
[End of loop]

Step-3  set PTR= STACK[TOP and TOP=TOP-1.[pops node from STACK].

Step-4 Repeat step 5 to 7 while PTR is not equal to Null; [backtracking].

Step-5 Apply PROCESS to INFO[PTR],

Step-6 [RIGHT child?] if RIGHT[PTR] is not equal NULL then.
a)	Set PTR=RIGHT[PTR]
b)	Go to step 3.[End of if structure.]

Step-7 set PTR= STACK[TOP] and TOP=TOP-1. [pops node]
[End of step 4 loop]

Step-8 Exit.

3) Algorithm for Preorder

In this traversal first, traverse all the left external node starting with the leftmost subtree which is then followed by bubble-up all the external node and then traverse the right subtree starting at the left external node which is the followed by bubble-up all the internal nodes and lastly visit the root node.

PREORDER(  INFO, LEFT,RIGHT, ROOT)
Step-1 [initially push NULL onto stack and initialize PTR.]
  Set TOP=1 STACK[1]=NULL and PTR= ROOT.

Step-2 Repeat step 3 to 5 while PTR not equal NULL.

Step-3 Apply PROCESS to INFO[PTR].

Step-4 [RIGHT child?]
  If RIGHT[PTR] not equal NULL then [PUSH on STACK]
 Set TOP= TOP+1 and STACK[TOP]= RIGHT[PTR]
[End of if structure.]

Step-5 [LEFT child?]
   If LEFT[PTR] not equal NULL then
  Set PTR= LEFT[PTR].
  Else [pop from STACK;]
Set PTR= STACK[TOP] and TOP=TOP+!;
[End of if structure]
[End of step 2 loop]

Step-6 Exit.