Hierarchical Datastructure – Iterative Tree Traversals

Iterative approach for Inorder Traversal

As we already know the definition of inorder traversal, we will directly jump into the algorithm. It is mostly similar to the preOrder traversal, only thing which matters is the order in which we push into the stack.

The very first thing is to check if the node i.e. root is not null. If it is null then return from the method, because there is nothing to traverse. We will consider the same tree for traversal and below is the pseudo code:
inorderPseudoCode
Let us start with an empty stack S. We have the node reference which points to the root in the beginning. Push the node and its left children in the stack one by one.

Now we run an iteration till our stack S is not empty, in each iteration of the loop we pop the node from the stack and assign it to the node reference and print the node value as well.

Evaluate if node has a current right child, assign the right child to the node reference. Now push the left children of the current node on to the stack. Repeat this till the stack is not empty.

Why do we do this?

Inorder traversal is about visiting the left children before visiting the root and then visit the right child. Hence, for every node we are pushing its hierarchy of left children into the stack.

Dry Run of the program

At this moment the node reference contains the ROOT.
Node reference contains ROOT which is not null, so push the ROOT into the stack, assign the left child of the ROOT i.e. P1 to the node reference.
Node reference contains P1 which is not null, so push P1 into the stack, assign the left child of P1 i.e. C1 to the node reference.
Node reference contains C1 which is not null, so push C1 into the stack, assign the left child of C1 i.e. L1 to the node reference.
Node reference contains L1 which is not null, so push L1 into the stack, assign the left child of L1 i.e. null to the node reference.

Node reference contains NULL,so break out of the first while loop. The stack looks like below:
2st_1
Outer Iteration 1:
The stack is not empty, pop L1 from the stack and assign it to the node reference.
Node reference contains L1. Also, print the value of node reference, hence we print L1.
Evaluate if current node L1 has a right child. No it doesn’t have one.
So outer Iteration 1 is over and we have already printed L1. Stack looks like the following:
2st_2
Outer Iteration 2:
The stack is not empty, pop C1 from the stack and assign it to the node reference.
Node reference contains C1. Also, print the value of node reference, hence we print C1.
Evaluate if current node C1 has a right child. No it doesn’t have one.
So outer Iteration 2 is over and we have already printed L1 and C1. Stack looks like the following:
2st_3
Outer Iteration 3:
The stack is not empty, pop P1 from the stack and assign it to the node reference.
Node reference contains P1. Also, print the value of node reference, hence we print P1.
Evaluate if current node P1 has a right child. Yes it has a right child C2.
Assign C2 to the node reference. Now push C2 on the stack and assign the left child of C2 i.e. L2 to the node reference.
As the node reference contains L2 which is not null, push L2 on to the stack and assign the left child of L2 i.e. NULL to the node reference.
As the node reference contains null, so move to the next outer Iteration and we have already printed L1, C1 and P1. The stack looks like the below:
2st_4
Outer Iteration 4:
The stack is not empty, pop L2 from the stack and assign it to the node reference.
Node reference contains L2. Also, print the value of node reference, hence we print L2.
Evaluate if current node L2 has a right child. No it doesn’t have one.
So outer Iteration 4 is over and we have already printed L1, C1, P1 and L2. Stack looks like the following:
2st_5
Outer Iteration 5:
The stack is not empty, pop C2 from the stack and assign it to the node reference.
Node reference contains C2. Also, print the value of node reference, hence we print C2.
Evaluate if current node C2 has a right child. No it doesn’t have one.
So outer Iteration 5 is over and we have already printed L1, C1, P1, L2 and C2 .Stack looks like the following:
st1_root
Outer Iteration 6:
The stack is not empty, pop ROOT from the stack and assign it to the node reference.
Node reference contains ROOT. Also, print the value of node reference, hence we print ROOT.
Evaluate if current node ROOT has a right child. Yes it has a right child P3.
Assign P3 to the node reference. Now push P3 on the stack and assign the left child of P3 i.e. C4 to the node reference.
As the node reference contains C4 which is not null, push C4 on to the stack and assign the left child of C4 i.e. NULL to the node reference.
As the node reference contains null, so move to the next outer Iteration and we have already printed L1, C1, P1, L2, C2 and ROOT. The stack looks like the below:
2st_6
Outer Iteration 7:
The stack is not empty, pop C4 from the stack and assign it to the node reference.
Node reference contains C4. Also, print the value of node reference, hence we print C4.
Evaluate if current node C4 has a right child. Yes it has a right child L5.
Assign L5 to the node reference. Now push L5 on the stack and assign the left child of L5 i.e. null to the node reference.

As the node reference contains null, so move to the next outer Iteration and we have already printed L1, C1, P1, L2, C2, ROOT and C4. The stack looks like the below:
2st_7
Outer Iteration 8:
The stack is not empty, pop L5 from the stack and assign it to the node reference.
Node reference contains L5. Also, print the value of node reference, hence we print L5.
Evaluate if current node L5 has a right child. No it doesn’t have one.
So outer Iteration 8 is over and we have already printed L1, C1, P1, L2, C2, ROOT, C4 and L5 .Stack looks like the following:
st7
Outer Iteration 9:
The stack is not empty, pop P3 from the stack and assign it to the node reference.
Node reference contains P3. Also, print the value of node reference, hence we print P3.
Evaluate if current node P3 has a right child. Yes it has a right child C5.
Assign C5 to the node reference. Now push C5 on the stack and assign the left child of C5 i.e. null to the node reference.

As the node reference contains null, so move to the next outer Iteration and we have already printed L1, C1, P1, L2, C2, ROOT, C4, L5 and P3. The stack looks like the below:
st10
Outer Iteration 10:
The stack is not empty, pop C5 from the stack and assign it to the node reference.
Node reference contains C5. Also, print the value of node reference, hence we print C5.
Evaluate if current node C5 has a right child. No it doesn’t have one.
So outer Iteration 10 is over and we have already printed L1, C1, P1, L2, C2, ROOT, C4, L5 and C5.
And now the stack is empty, so we completed the execution.

As a result we have already printed/visited all the nodes in an in order fashion.