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:
Below is the C++ program for the same:
• 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.
This 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);
}
}
@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).
Hi 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();
}
}