## Iterative PreOrder Tree Traversal (C++)

PreOrder Traversal means displaying the root first, then traverse left subtree, and then traverse the right subtree. Because a stack is LIFO (last in first out), we need to be careful how we insert the nodes into the stack. We can think of it this was LIFO (last in first out) is equivalent to FILO (first in last out). We know the right subtree will be last to be evaluated, the right subtree should be the first to be “pushed” into the stack. Then the left subtree needs to be pushed into the stack. Finally we print out the root’s data.

Stack Space: Proportional to the height of the tree

```#include <iostream>
#include <cstdio>
#include <stack>
#include <string>

using namespace std;

typedef struct _TreeNode {
char data;
struct _TreeNode *left;
struct _TreeNode *right;
} Node;

void iterativePreOrderTraverse(Node *root) {
stack<Node *> nodes;
Node *currNode;

if(root)
nodes.push(root);

while(!nodes.empty()) {
currNode = nodes.top();
nodes.pop();
// Test if right subtree exists and push to stack if it exists
Node *rightNode = currNode->right;
if (rightNode)
nodes.push(rightNode);
// Test if left subtree exists and push to stack if it exists
Node *leftNode = currNode->left;
if (leftNode)
nodes.push(leftNode);
// Print root value
printf("%c ", currNode->data);
}
}```
This entry was posted in Coding and tagged , , . Bookmark the permalink.