Tree: PreOrder Traversal without Recursion

Problem: Write the code for pre-order traversal of a binary tree without recursion.

Solution: Most problems involving binary trees can be solved by using recursion. Recursion is inherent to trees. But, keep in mind that recursion has a memory overhead because of the additional stack space required for the recursive method calls. Sometime interviewers will ask to solve problems related to trees without using recursion. This can sometimes make the problem challenging. In this problem, even though we will not use recursion explicitly, we will use the Stack data structure that emulates what recursion does.

Code:

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

void Pre-Order-Traversal-Non-Recursive(Node * root)
{
   Stack nodeStack;
   nodeStack.Push(root);
   
   // while stack is not empty
   while(nodeStack.Count > 0)
   {
      Node * currentNode = nodeStack.Pop();
      printf("%d\n", currentNode->data);
      nodeStack.Push(currentNode->right);
      nodeStack.Push(currentNode->left);
   }
}

Note: This implementation, even though avoids recursion, does not take any less memory compared to the recursive method since we are using an external stack to emulate recursion.