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.