top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to traverse a TREE without recursion?

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

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social 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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...