Home > Computer Programming, Problem Solving/Puzzles > Iterative In-Order Tree Traversal !

Iterative In-Order Tree Traversal !

Hello !

All the DS Techies would be familiar with the famous In-Order tree traversal. However most of the algorithms for traversals are recursive. Once my friend was asked to write an In-Order tree traversal without recursion. I was also asked the same question and I wrote the following algorithm.

InOrder_TreeTraversal()
{
prev = null;
current = root;
next = null;

while( current != null )
{
if(prev == current.parent)
{
prev = current;
next = current.left;
}

if(next == null || prev == current.left)
{
print current.value;
prev = current;
next = cuurent.right;
}

if(next == null || prev == current.right)
{
prev = current;
next = cuurent.parent;
}

current = next;
}
}

The idea is to use another link which is a link to the parent node. So the above code do the same.

Regards,
Haroon Saeed

Advertisements
  1. June 25, 2007 at 12:12 am
  2. February 1, 2008 at 3:30 am

    Thanks boyse81f1b05445bc1e774ae3eb926506764

  3. lol
    February 2, 2008 at 8:19 am
  4. jz
    April 30, 2008 at 1:00 pm

    Should’ve used print statements in the above code.

    Here is my version of iterative in order

    void InorderTraversal(Node *root){

    if(!root){
    return;
    }

    Node *last = NULL;
    Node *cursor = root;
    while(true){

    if(last){ //going up
    if(cursor->left && cursor->left == last){
    last = NULL;
    cout<data;
    if(!MoveCursorRight(&cursor)){
    last = cursor;
    if(!MoveCursorUp(&cursor)){
    return;
    }
    }
    }
    else{
    last = cursor;
    if(!MoveCursorUp(&cursor)){
    return;
    }
    }
    }
    else{ //going down
    while(cursor->left){
    cursor=cursor->left;
    }
    cout<data;

    last = NULL;
    if(!MoveCursorRight(&cursor)){
    last = cursor;
    if(!MoveCursorUp(&cursor)){
    return;
    }
    }
    }
    }

    bool MoveCursorRight(Node **cursor){
    if(*cursor->right){
    *cursor = *cursor->right;
    return true;
    }
    return false;
    }

    bool MoveCursorUp(Node **cursor){
    if(*cursor->parent){
    *cursor = cursor->parent;
    return true;
    }
    return false;
    }

    }

  5. Sathyanarayan B
    June 27, 2008 at 9:55 am

    Surely an excellent job, But I think U should be writing some comments, and have some indentations with it.

  6. HisTomness
    May 15, 2009 at 5:50 pm

    Small correction required in the first check:

    if(prev == NULL || prev == current.parent)

    Otherwise this algorithm only traverses the left side of the tree.

  7. HisTomness
    May 15, 2009 at 5:52 pm

    Disregard previous correction. I realize that at the outset prev == current.parent == null.

  8. September 24, 2009 at 4:07 pm

    Using a parent pointer (above methods) are one iterative method. Some others are a stack with a visited value on each node, or a visited value stored in the stack.

    Did some comparison of in-order iterative approaches using Python:
    http://m2mooo.tripod.com/program/inorder.html

    Recursive was fastest, followed by visited flag, then having a auxiliary stack for visited flag values. Simple was better.

  1. June 11, 2010 at 5:53 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: