Hierarchical Datastructure – Iterative Tree Traversals

Introduction

This is the second article in the Tree Traversals – Online Classes.

This is the sixth article in the series of non-linear data structures, to read more about the previous article, please check the topic Hierarchical Datastructure – Tree Traversals. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

We are already done with the constructing a binary tree and doing basic operations like creating a tree, adding a node, removing a node and all the traversals. There are situations when we get little confused using the recursive approaches of traversals. To make it more simple, I will try to demonstrate with the help of Iterative Tree Traversals

Iterative approach for Preorder Traversal

As we already know the definition of preorder traversal, we will directly jump into the algorithm, its explanation and implementation. To traverse a tree in preorder fashion we will employ a stack and we pass the root node of the tree into the preOrder routine/method.

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 below tree for traversal and below is the pseudo code for the same:
tree2

Pseudo Code

preorderPseudoCode
So let us start with an empty stack S and push the ROOT in there, the stack looks like the image below:
st1_root

Now we run an iteration till our stack S is not empty, in each iteration of the loop we pop a node from the stack and visit it(print it). Then we check if the node has a left right child we push the right child on the stack and then if the node has a left child, we put the left child on the stack.

We keep executing this set of statements till the stack contains at least one element.

Dry Run of the program

At this moment the stack contains the ROOT.

Note: Just in case if you are not aware, the stack is a data structure where elements can be pushed and popped only from the top.
Iteration 1:
The stack is not empty we pop the ROOT from the Stack (making the stack empty), print the ROOT.
Check if the root has a right child, yes it has P3. Push P3 on the stack.
Check if the root has a left child, yes it has P1. Push P1 on the stack.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT.
st2
Iteration 2:
The stack is not empty, we pop P1 from the stack, print P1.
Check if the P1 has a right child, yes it has C2. Push C2 on the stack.
Check if the P1 has a left child, yes it has C1. Push C1 on the stack.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT and P1.
st3
Iteration 3:
The stack is not empty, we pop C1 from the stack, print C1.
Check if the C1 has a right child, no it doesn’t have one.
Check if the C1 has a left child, yes it has L1. Push L1 on the stack.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1 and C1.
st4
Iteration 4:
The stack is not empty, we pop L1 from the stack, print L1.
Check if the L1 has a right child, no it doesn’t have one.
Check if the L1 has a left child, no it doesn’t have one.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1 and L1
st5
Iteration 5:
The stack is not empty, we pop C2 from the stack, print C2.
Check if the C2 has a right child, no it doesn’t have one.
Check if the C2 has a left child, yes it has L1. Push L2 on the stack.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1, L1 and C2
st6
Iteration 6:
The stack is not empty, we pop L2 from the stack, print L2.
Check if the L2 has a right child, no it doesn’t have one.
Check if the L2 has a left child, no it doesn’t have one.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1, L1, C2 and L2
st7
Iteration 7:
The stack is not empty, we pop P3 from the stack, print P3.
Check if the P3 has a right child, yes it has C5. Push C5 on the stack.
Check if the P3 has a left child, yes it has C4. Push C4 on the stack.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1, L1, C2, L2 and P3
sst8
Iteration 8:
The stack is not empty, we pop C4 from the stack, print C4.
Check if the C4 has a right child, yes it has L5. Push L5 on the stack.
Check if the C4 has a left child, no it doesn’t have one.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1, L1, C2, L2, P3 and C4
st9
Iteration 9:
The stack is not empty, we pop L5 from the stack, print L5.
Check if the L5 has a right child, no it doesn’t have one.
Check if the L5 has a left child, no it doesn’t have one.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1, L1, C2, L2, P3, C4 and L5
st10
Iteration 10:
The stack is not empty, we pop C5 from the stack, print C5.
Check if the C5 has a right child, no it doesn’t have one.
Check if the C5 has a left child, no it doesn’t have one.
The iteration is over. At the end of the iteration The stack is like below and we also have already printed the ROOT, P1, C1, L1, C2, L2, P3, C4, L5 and C5

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