# How to traverse a TREE without recursion?

1,536 views
How to traverse a TREE without recursion?
posted Nov 28, 2013

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.

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;
}
}
}
``````
This is Depth first way of searching. Depends on usage other option would be Breadth First Search.
Similar Questions

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

Given Tree

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

Expected Output
6 8 12 13