This is a C++ Program to print preorder traversal of a given binray tree without using recursion.

Here is source code of the C++ Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include <stdlib.h>`

`#include <stdio.h>`

`#include <iostream>`

`#include <stack>`

using namespace std;

`/* A binary tree node has data, left child and right child */`

`struct node`

`{`

int data;

struct node* left;

struct node* right;

};

`/* Helper function that allocates a new node with the given data and`

`NULL left and right pointers.*/`

struct node* newNode(int data)

`{`

struct node* node = new struct node;

node->data = data;

node->left = NULL;

node->right = NULL;

return (node);

`}`

`// An iterative process to print preorder traversal of Binary tree`

void iterativePreorder(node *root)

`{`

`// Base Case`

if (root == NULL)

return;

`// Create an empty stack and push root to it`

stack<node *> nodeStack;

nodeStack.push(root);

`/* Pop all items one by one. Do following for every popped item`

`a) print it`

`b) push its right child`

`c) push its left child`

`Note that right child is pushed first so that left is processed first */`

while (nodeStack.empty() == false)

`{`

`// Pop the top item from stack and print it`

struct node *node = nodeStack.top();

printf("%d ", node->data);

nodeStack.pop();

`// Push right and left children of the popped node to stack`

if (node->right)

nodeStack.push(node->right);

if (node->left)

nodeStack.push(node->left);

`}`

`}`

int main()

`{`

`/* Constructed binary tree is`

`10`

`/ \`

`8 2`

`/ \ /`

`3 5 2`

`*/`

struct node *root = newNode(10);

root->left = newNode(8);

root->right = newNode(2);

root->left->left = newNode(3);

root->left->right = newNode(5);

root->right->left = newNode(2);

cout<<"Pre order traversal: ";

iterativePreorder(root);

return 0;

`}`

Output:

$ g++ NonRecursivePreorder.cpp $ a.out Pre order traversal: 10 8 3 5 2 2 ------------------ (program exited with code: 0) Press return to continue

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.