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.