In last post we have seen the iterative method of post order traversal of a binary tree. In this post we see how to find an preorder traversal of a Binary tree.

**Recursive solution:**

void preOrderTraversal(TreeNode *root)

{

if (!root) return;

cout << root->data;

preOrderTraversal(root->left);

preOrderTraversal(root->right);

}

**Iterative Solution:**

**Algorithm:**

• Push the root node to the stack.

• while stack is not empty

. • Pop a node from the stack, and enque It in the queue (or just print it, skip last step if you are just printing it).

. • Push its right child followed by its left child to the child stack.

• end while

• Now the Queue would have all the nodes ready to be traversed in pre-order. Deque the nodes from the Queue one by one and you will have the pre order traversal of the tree.

Below is the C++ program for the same:

void preOrderTraversalIterative(BinaryTree *root)

{

if (!root) return;

stack<BinaryTree*> s;

Queue<BinaryTree*> output;

s.push(root);

while (!s.empty()) {

BinaryTree *curr = s.top();

//Enque Current element in Output queue or just print

output.enque(curr);

s.pop();

if (curr->right)

s.push(curr->right);

if (curr->left)

s.push(curr->left);

}

//skip this while loop if you were printting earlier

while (!output.empty()) {

cout << output.deque()->data << " ";

}

}

This works just magically, try an example yourself and you will see how it works.

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
AnonymousThis is a simple iterative solution of preorder traversal using only one stack

The idea is push root into stack

Pop from stack

Print the data

then push root's right into stack, then push root's left into stack

Continue till the stack is not empty

void preorder(btree *root)

{

Stack s=new Stack();

if(root==NULL)

return;

s.push(root);

while(!s.isEmpty())

{

btree *r=s.pop();

cout<<"\t"<data;

if(r->right!=NULL)

s.push(r->right);

if(r->left!=NULL)

s.push(r->left);

}

}

Akash@Anonymous: This is what I have written in my algorithm. It seems that you missed the part written in parenthesis.

• Pop a node from the stack, and enque It in the queue (or just print it, skip last step if you are just printing it).

UnknownHi Akash I wrote this in a slightly way, it works correctly for me. It would be great if you help me point out any error.

void preorder(node* root)

{

stack S;

for(node* iter = root; iter || !S.empty(); iter = iter->right)

{

while(iter)

{

cout << iter->key << " ";

S.push(iter);

iter = iter->left;

}

iter = S.top(), S.pop();

}

}