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.

8 comments:

  1. For the pre-order, you will have to process the nodes as follows: Root(Node)->Left->Right, while you have it as Root(Node)->Right->Left.

    ReplyDelete
    Replies
    1. he is using stack, so the right node should be pushed before left node

      Delete
  2. isnt't null check required ?? when pusing elements in stack

    ReplyDelete
  3. ya its required

    ReplyDelete
  4. @all...Please understand the logic...he is using stack so root->right->left means
    he will print root first then left will be printed as left is at the top of the stack.

    ReplyDelete
  5. it is showing some errors

    ReplyDelete
  6. Node * currentNode = nodeStack.Pop();
    if(currentNode != null) {
    printf("%d\n", currentNode->data);
    nodeStack.Push(currentNode->right);
    nodeStack.Push(currentNode->left);
    }
    would check the null otherwise it throws error.

    ReplyDelete
  7. Check the null in main with throwing an Exception :)

    ReplyDelete