top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to traverse a TREE without recursion?

+2 votes
2,129 views
How to traverse a TREE without recursion?
posted Nov 28, 2013 by Neelam

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Following is the algorithm

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
     a) Pop the top item from stack.
     b) Print the popped item, set current = current->right
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

1 Answer

+2 votes

Thanks Jai, following is C++ implementation

void inOrderTraversalWithOutStack(struct node* node)    {
    std::stack<struct node*> stk;
    struct node* current = node;
    while(current)  {
        while(current)  {
            stk.push(current);
            current = current->left;
        }
        while(current == NULL && !stk.empty())  {
            current = stk.top();
            stk.pop();
            printf("%d \t", current->data);
            current = current->right;
        }
    }
}
answer Nov 28, 2013 by Salil Agrawal
This is Depth first way of searching. Depends on usage other option would be Breadth First Search.
Similar Questions
0 votes

How to traverse a binary search tree diagonally? Any sample algo/code?

+2 votes

Given Tree

          6
       /     \
     7        8
   /   \     /  \
  9    10  11    12
                  \
                   13

Expected Output
6 8 12 13

...