Pre-Order Tree Traversal Without Recursion : Pseudo Code

We very well know how to traverse a binary search tree using the concept of recursion. If you don't, click on this link. Now, the challenge is to traversal the same tree in pre-order without the use of recursion. It can be done easily by the use of a stack. The following pseudo code shows us how to do it. The push and pop of the stacks are the basic push and pop operations used in any stack implementation.

Pseudo Code :

typedef struct _node
{
   int data;
   struct _node * left;
   struct _node * right;
} Node;

void PreOrderTraversalNonRecursive(Node * root)
{
   Stack nodeStack;
   nodeStack.Push(root);
  
   //While stack is not empty
   while(nodeStack.Count > 0)
   {
      Node * currentNode = nodeStack.Pop();
      print (currentNode->data);
      nodeStack.Push(currentNode->right);
      nodeStack.Push(currentNode->left);
   }
}