Perform PreOrder traversal on a Binary Tree by without Recursion

Question:

Given a binary tree root node, perform PreOrder traversal by using stacks.

Example:

Consider the image given below:

PreOrder Traversal(Root, Left, Right): 16 10 7 15 25 18 30

Now lets see how to perform Pre Order Traversal: (Root, Left, Right)

In pre Order traversal, first root node will be printed, then left node then the right node.

If we have only one node as below, we print that node.

If we have a tree with 3 nodes as below:

Pass 1:

We first will insert root node “16” into the stack.

Stack = 16.

Now, we pop the node and print the value.

Display = 16

Now we go to the right child of node “16” and insert that in to the stack.

Stack = 25

Now we go to the left child of node “16” and insert that in to the stack.

Stack = 25, 10

This completes the first iteration.

Pass 2:

Now in the 2nd iteration “node 10” is popped out and displayed.

Stack = 25

Display = 16, 10

Now, it will check if “node 10” has left or right child, if it has it will pushed into stack, else it will continue.

As it is not having any children it will move to third iteration.

Pass 3:

Now in the 2nd iteration “node 25” is popped out and displayed.

Stack =

Display = 16, 10, 25

Now, it will check if “node 25” has left or right child, if it has it will pushed into stack, else it will continue.

As it is not having any children it will move to third iteration.

So the final output is = 16, 10, 25. Hence pre-order traversal.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void print_pre_order(struct Node *root) 
{ 
    stack<Node *> s; 
    s.push(root); 

    while (s.empty() ==  false) 
    {   
        Node *curr = s.top(); 
        cout<<curr->data <<" ";
        s.pop(); 

        if(curr->right != NULL) 
        {
            s.push(curr->right);
        }

        if(curr->left != NULL) 
        {
            s.push(curr->left);
        } 

    } 
} 


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"PreOrder Traversal(Root, Left, Right) = " ; print_pre_order(root); cout<<endl; 


    return 0;  
}  

Output:

PreOrder Traversal(Root, Left, Right) = 16 10 7 15 25 18 30