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);
  }
}
Advertisements
This entry was posted in Coding and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s