I had a recent interview where I was asked to implement and in-order
traversal of a binary tree.  I was able to provide the recursive
solution for this problem.  The interviewer then requested that I
provide a non-recursive solution as well.

I knew this solution would involve the use of a stack or some other
similar structure.  However, the solution was not obvious to me and
time did not allow me to complete the problem.

I have since gone back and reworked the problem.  Here is a C++
solution I came up with using the STL that seems to work:

void PrintTree
(
    Node* node
)
{
    if(NULL == node){
        return;
    }

    std::stack<Node*> nodeStack;

    nodeStack.push(node);

    bool left = true;
    while(false == nodeStack.empty()){
        node = nodeStack.top();
        if(left){
            if(NULL != node->left){
                nodeStack.push(node->left);
            }
            else{
                left = false;
            }
        }
        else{
            nodeStack.pop();
            std::cout << node->value << '\n';
            if(NULL != node->right){
                nodeStack.push(node->right);
                left = true;
            }
        }
    }
}

How effective is this solution?

On Fri, 22 Feb 2008 11:09:16 -0800 (PST), tron.thomas@verizon.net
wrote:

>I had a recent interview where I was asked to implement and in-order
>traversal of a binary tree.  I was able to provide the recursive
>solution for this problem.  The interviewer then requested that I
>provide a non-recursive solution as well.
>
>I knew this solution would involve the use of a stack or some other
>similar structure.  However, the solution was not obvious to me and
>time did not allow me to complete the problem.
>
>I have since gone back and reworked the problem.  Here is a C++
>solution I came up with using the STL that seems to work:

Perhaps I shouldn't mention this, but if you are allowed to
reverse links temporarily, you can do it without a stack.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

On Feb 22, 2:09 pm, tron.tho...@verizon.net wrote:
> I had a recent interview where I was asked to implement and in-order
> traversal of a binary tree.  I was able to provide the recursive
> solution for this problem.  The interviewer then requested that I
> provide a non-recursive solution as well.
>
> I knew this solution would involve the use of a stack or some other
> similar structure.

Any operation that's not tail recursive will pretty much require a
stack if you want to simulate recursion.

> I have since gone back and reworked the problem.  Here is a C++
> solution I came up with using the STL that seems to work:
>
> void PrintTree
> (
>     Node* node
> )
> {
>     if(NULL == node){
>         return;
>     }
>
>     std::stack<Node*> nodeStack;
>
>     nodeStack.push(node);
>
>     bool left = true;
>     while(false == nodeStack.empty()){
>         node = nodeStack.top();
>         if(left){
>             if(NULL != node->left){
>                 nodeStack.push(node->left);
>             }
>             else{
>                 left = false;
>             }
>         }
>         else{
>             nodeStack.pop();
>             std::cout << node->value << '\n';
>             if(NULL != node->right){
>                 nodeStack.push(node->right);
>                 left = true;
>             }
>         }
>     }
>
> }
>
> How effective is this solution?

Looks good to me, but personally I find your process unintuitive,
probably because of the left flag. I think the whole process is easier
to grok without that extra state variable, so here's an alternative
solution that does basically the same thing:

void PrintTree ( Node *node )
{
  std::stack<Node*> up;

  while ( node != 0 ) {
    while ( node != 0 ) {
      if ( node->right != 0 )
        up.push ( node->right );

      up.push ( node );
      node = node->left;
    }

    node = up.top();
    up.pop();

    while ( !up.empty() && node->right == 0 ) {
      std::cout<< node->value <<'\n';
      node = up.top();
      up.pop();
    }

    std::cout<< node->value <<'\n';

    if ( up.empty() )
      break;

    node = up.top();
    up.pop();
  }
}

tron.thomas@verizon.net writes:

> I had a recent interview where I was asked to implement and in-order
> traversal of a binary tree.  I was able to provide the recursive
> solution for this problem.  The interviewer then requested that I
> provide a non-recursive solution as well.
>
> I knew this solution would involve the use of a stack or some other
> similar structure.  However, the solution was not obvious to me and
> time did not allow me to complete the problem.

See one of my solutions at:
        http://adtinfo.org/libavl.html/Iterative-Traversal-of-a-BST.html

-- 
"If a person keeps faithfully busy each hour of the working day, he
 can count on waking up some morning to find himself one of the
 competent ones of his generation."
--William James

<tron.thomas@verizon.net> wrote in message 
news:c3156442-6541-46f0-8220-603e64ca9625@h11g2000prf.googlegroups.com...
>I had a recent interview where I was asked to implement and in-order
> traversal of a binary tree.  I was able to provide the recursive
> solution for this problem.  The interviewer then requested that I
> provide a non-recursive solution as well.
>
> I knew this solution would involve the use of a stack or some other
> similar structure.  However, the solution was not obvious to me and
> time did not allow me to complete the problem.
>

hmm...


> I have since gone back and reworked the problem.  Here is a C++
> solution I came up with using the STL that seems to work:
>
> void PrintTree
> (
>    Node* node
> )
> {
>    if(NULL == node){
>        return;
>    }
>
>    std::stack<Node*> nodeStack;
>
>    nodeStack.push(node);
>
>    bool left = true;
>    while(false == nodeStack.empty()){
>        node = nodeStack.top();
>        if(left){
>            if(NULL != node->left){
>                nodeStack.push(node->left);
>            }
>            else{
>                left = false;
>            }
>        }
>        else{
>            nodeStack.pop();
>            std::cout << node->value << '\n';
>            if(NULL != node->right){
>                nodeStack.push(node->right);
>                left = true;
>            }
>        }
>    }
> }
>
> How effective is this solution?
>

if it works, it works...

actually, if your nodes have an 'up' link, you don't even need a stack...

untested, just made up right here:
while(1)
{
    if(node->left) { node=node->left; continue; }
    if(node->right) { node=node->right; continue; }

    if(!node->left && !node->right)    //if leaf
        cout << node->value << '\n';    //print value (I usually use printf, 
and C, myself...)

    if(node==node->up->left && node->up->right)
    {
        cout << node->up->value << '\n';    //if nodes have values
        node=node->up->right;
        continue;
    }

    while(node->up && !(node==node->up->left && node->up->right))
        node=node->up;
    if(!node->up)break;
    cout << node->up->value << '\n';    //if nodes have values
    node=node->up->right;
}

On Feb 22, 2:09=A0pm, tron.tho...@verizon.net wrote:
> I had a recent interview where I was asked to implement and in-order
> traversal of a binary tree. =A0I was able to provide the recursive
> solution for this problem. =A0The interviewer then requested that I
> provide a non-recursive solution as well.
>
> I knew this solution would involve the use of a stack or some other
> similar structure. =A0However, the solution was not obvious to me and
> time did not allow me to complete the problem.
>
> I have since gone back and reworked the problem. =A0Here is a C++
> solution I came up with using the STL that seems to work:
>
> void PrintTree
> (
> =A0 =A0 Node* node
> )
> {
> =A0 =A0 if(NULL =3D=3D node){
> =A0 =A0 =A0 =A0 return;
> =A0 =A0 }
>
> =A0 =A0 std::stack<Node*> nodeStack;
>
> =A0 =A0 nodeStack.push(node);
>
> =A0 =A0 bool left =3D true;
> =A0 =A0 while(false =3D=3D nodeStack.empty()){
> =A0 =A0 =A0 =A0 node =3D nodeStack.top();
> =A0 =A0 =A0 =A0 if(left){
> =A0 =A0 =A0 =A0 =A0 =A0 if(NULL !=3D node->left){
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 nodeStack.push(node->left);
> =A0 =A0 =A0 =A0 =A0 =A0 }
> =A0 =A0 =A0 =A0 =A0 =A0 else{
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 left =3D false;
> =A0 =A0 =A0 =A0 =A0 =A0 }
> =A0 =A0 =A0 =A0 }
> =A0 =A0 =A0 =A0 else{
> =A0 =A0 =A0 =A0 =A0 =A0 nodeStack.pop();
> =A0 =A0 =A0 =A0 =A0 =A0 std::cout << node->value << '\n';
> =A0 =A0 =A0 =A0 =A0 =A0 if(NULL !=3D node->right){
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 nodeStack.push(node->right);
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 left =3D true;
> =A0 =A0 =A0 =A0 =A0 =A0 }
> =A0 =A0 =A0 =A0 }
> =A0 =A0 }
>
> }
>
> How effective is this solution?

On Feb 22, 2:09 pm, tron.tho...@verizon.net wrote:
> I had a recent interview where I was asked to implement and in-order
> traversal of a binary tree.  I was able to provide the recursive
> solution for this problem.  The interviewer then requested that I
> provide a non-recursive solution as well.
>
> I knew this solution would involve the use of a stack or some other
> similar structure.  However, the solution was not obvious to me and
> time did not allow me to complete the problem.
>
> I have since gone back and reworked the problem.  Here is a C++
> solution I came up with using the STL that seems to work:
>
> void PrintTree
> (
>     Node* node
> )
> {
>     if(NULL =3D=3D node){
>         return;
>     }
>
>     std::stack<Node*> nodeStack;
>
>     nodeStack.push(node);
>
>     bool left =3D true;
>     while(false =3D=3D nodeStack.empty()){
>         node =3D nodeStack.top();
>         if(left){
>             if(NULL !=3D node->left){
>                 nodeStack.push(node->left);
>             }
>             else{
>                 left =3D false;
>             }
>         }
>         else{
>             nodeStack.pop();
>             std::cout << node->value << '\n';
>             if(NULL !=3D node->right){
>                 nodeStack.push(node->right);
>                 left =3D true;
>             }
>         }
>     }
>
> }
>
> How effective is this solution?

This is fine.  But here's a leg up for next time:  If you know a
recursive solution, you can _always_ work out a non-recursive solution
by following some simple rules.  These amount to simulating the stack
manipulation that the compiler will cause in the recursive version.

In this case we start with:

void walk(Node *t)
{
  if (t) {
    walk(t->left);
    visit(t);
    walk(t->right);
  }
}

First eliminate the tail recursive call.   Every tail call is a loop
in disguise.

void walk(Node *t)
{
tail_call:
  if (t) {
    walk(t->left);
    visit(t);
    t =3D t->right;
    goto tail_call;
  }
}

Pretty this up by replacing goto with while:

void walk(Node *t)
{
  while (t) {
    walk(t->left);
    visit(t);
    t =3D t->right;
  }
}

Now there is only one recursive call site.  This is a simple case.
You simulate by saving the value of the current arg on a stack,
replacing with the new value, then jumping to the start as before.
When the function is about to return, pop an arg off the stack and
jump to the return original return site ... unless the stack is empty,
of course.  In that case you do the actual return.  It's easier to
code than say:

void walk(Node *t)
{
recursive_call:
  while (t) {
    push(t);
    t =3D t->left;
    goto recursive_call;
    // old recursive call was here:  walk(t->left);
return_site:
    visit(t);
    t =3D t->right;
  }
  // simulate a return from recursive call
  if (! stack_empty() ) {
    t =3D pop();
    goto return_site;
  }
}

Again you can clean this up by eliminating the gotos... I'll do this
in steps so you can see what I'm doing:

void walk(Node *t)
{
recursive_call:
  while (t) {
    push(t);
    t =3D t->left;
    goto recursive_call;
return_site:
    // two lines moved below with no change in meaning
  }
  if (! stack_empty() ) {
    t =3D pop();
    visit(t);
    t =3D t->right;
    goto return_site;
  }
}

void walk(Node *t)
{
recursive_call:
  while (t) {
    push(t);
    t =3D t->left;
    // elimination has no effect:  goto recursive_call;
  }
  if (! stack_empty() ) {
    t =3D pop();
    visit(t);
    t =3D t->right;
    goto recursive_call;  // change in target is no change in meaning
  }
}

Now replace the remaining goto with another loop, and you're done.

void walk(Node *t)
{
  for (;;) {
    while (t) {
      push(t);
      t =3D t->left;
    }
    if ( stack_empty() ) break;
    t =3D pop();
    visit(t);
    t =3D t->right;
  }
}

I have not tested this code, but it ought to be right.  This technique
always works except of course when you make an "algebra" mistake while
rearranging code.  If I did that here, I know you can clean up the
mess.

A note:  If you have more than one recursive call site, you must also
record in the stack a "return address" -- a small integer that's used
to choose which return site to jump to during the simulated return.
If the recursive procedure has multiple arguments, you must watch out
not to redefine one that's still needed to calculate another; careful
sequencing and introducing temps is sometimes necessary.