# Preorder Traversal of Binary Tree Using Stack

“** Preorder Traversal of Binary Tree Using Stack**” is an important traversal algorithm of tree data structure. Here, we are given a binary tree and our task is to traverse the given binary tree in preorder fashion using stack data structure.

Preorder Traversal:

- Visit Root Node and Print it.
- Visit Left Subtree
- Visit Right Subtree

We have already discussed recursive implementation here. Now, the iterative implementation of the same recursive solution will be discussed here.

The steps required to implement preorder traversal of Binary Tree Using Stack are as follows:

- Create an empty stack and push root node into it.
- Perform following operation until stack is not empty:
- Pop an element from stack and print it.
- Push Right Node, if exist, into the stack.
- Push Left Node, if exist, into the stack.

#### C++ Program to Implement Preorder traversal of Binary Tree Using Stack is as follows:

```
/* C++ Program to implement preorder traversal of binary tree using stack*/
#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;
/* Function to implement Preorder Traversal */
void preorder(Node *root)
{
/* Check Base Condition */
if(root == NULL)
return;
/* Create an Empty Stack */
stack <Node *> st;
/* Push root Node into it */
st.push(root);
while(!st.empty())
{
/* Pop and print top node */
Node *temp = st.top();
st.pop();
cout<<temp -> data<<" ";
/* Push Right Child, if exists */
if(temp -> right)
st.push(temp -> right);
/* Push Left Child, if exists */
if(temp -> left)
st.push(temp -> left);
}
}
int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = NULL;
root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);
/* Calling function to perform preorder traversal*/
cout<<"The Preorder Traversal of the Given Binary Tree is: ";
preorder(root);
}
```

**OUTPUT:**

The Preorder Traversal of the Given Binary Tree is: 1 2 4 5 8 3 6 9 7

**Related Posts:**

**Inorder Tree Traversal Using Stack****Postorder Tree Traversal Using Stack****Vertical Order Tree Traversal****Top View of Binary Tree****Bottom View of Binary Tree****Delete Complete Binary Tree****Check if two trees are mirror Trees of Each Other****Convert Binary Tree to its Mirror Tree****Check if Binary Tree is Symmetric or Not****Print All Root to Leaf Paths in a Binary Tree****Introduction to Tree Data Structure****Binary Tree Traversals****Print All Leaf Nodes of a Binary Tree****Count Number of Nodes in a Binary Tree****Print Alternate Levels of Binary Tree****Maximum Width of Binary Tree****Level Order Tree Traversal****Left View of Binary Tree****Right View of Binary Tree****Compute Height of Binary Tree**