Iterative way of doing Pre-Order Traversal of a Binary Tree using STACK in C++

Let’s get to the point, you are here to know the iterative approach. Let’s discuss it.
Well let’s see what we need :

1. Binary Tree

2. Stack

Ok so Let’s quickly go through this image and get it clear what exactly is a pre-order traversal:

We need a Stack that can store the node and its count as a pair.

So here we declare a stack now we are going to perform certain operations till it gets empty, but before that, we are going to push the root element and its count

Great we have one element in the stack. Now we will start our loop condition is it will run till it gets empty.

Right!!,

Now there are three possible values of the count 0,1,2;
0 → Node is not visited yet.

1 → Print the value of that node. In addition to that, We are supposed to push its children in this case.

2 → Pop that pair from the stack.

So when we pick the top element of the stack we got a pair out of which we will extract the node and its count.

Now the situation is (node,count) →(1,1). now since the count is 1 we are going to print and push its children

Now when you will pick the top element, it’s the left child of that root node right? since it is (2,0) and when we increase its count it became (2,1) now we are going to print it and push its children. The same process goes on.

A time comes when the node has no children so you ain’t gonna push anything you again visit the same element and increase the count and it will become 2 as soon as it becomes 2 you are going to pop it.

That’s it!! This is how you are going to print the binary tree in Pre-order.