Pre Order traversal - Recursive and Iterative solution

Example
Consider the tree:
div class="separator" style="clear: both; text-align: center;">

To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Recursive solution

preorder(N *root)
{
  if(root)
  {
    printf("Value : [%d]", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}

Iterative solution

In some ways this is the simplest to understand initially.  However, even though each node is processed before the subtrees, it still requires that some information be retained while moving down the tree.  In the example
above, the * is processed first, then the left sub-tree followed by the right subtree.  Therefore, processing must return to the right sub-tree after finishing the processing of the left subtree.

In the examples given, suppose the the processing involved in the traversal is to print out the information stored in each node.Since movement is down the left side of the tree beginning at the root, information on what is to the right must be kept in order to complete the traversal of the right side of any subtree.  The obvious ADT for such information is a stack.   Because of its LIFO structure, it will be possible to get the information about the right subtrees back in the reverse order in which it was encountered.

The process of doing a pre-order traversal iteratively then has the following steps (assuming that a stack is available to hold pointers to the appropriate nodes):

1. push NULL onto the stack
2. start at the root and begin execution
3. write the information in the nodeN
4. if the nodeN-> right != NULL , push the pointer onto the stack
We push right one first as we need it last
5. if the nodeN -> left !=  NULL move the pointer to the node on the left
6. if the nodeN->left == NULL pop the stack
7. repeat steps 3 to 7 until no nodes remain


Using array indirectly as stack

void iterativePreorder(node *root)
{
 node *save[100];
 int top = 0;
 if (root == NULL)
 {
  return;
 }

 save[top++] = root;
 
 while (top != 0)
 {
  root = save[--top];
  printf("[%d] ", root->value);
  if (root->right != NULL)
   save[top++] = root->right;
   if (root->left != NULL)
    save[top++] = root->left;
 }
}

Using proper stack ( for clarity)

void preOrderNonRecursive(node* root) {
    if (!root) {
       return;
    }
    Stack<node*> t = new Stack<node*>();
    t.Push(root);
    while (t.Size() > 0) {
        node* top = t.Pop();
        printf("%d", top->value);
        if (top->right != null) {
            t.Push(top->right);
        }
        if (top->left != null) {
            t.Push(top->left);
        }
    }
}

Running the dry run on the above tree :
push root
stack 6

pop 6, push 8 2
stack 8 2

pop 2, push 5, 1
stack 8 5 1

pop 1,
stack 8 5

pop 5,
stack 8

pop 8, push 7
stack 7

pop 7

So have a look at all pop-order
6 2 1 5 8 7