Recursive to Iterative algorithms

hi. is it possible to write an iterative version of the post-order and in-order binary tree traversal algorithms? I know how to do the one for preorder using stacks, but I can't get my head around the other two.

please help
friend,

It's really simple: think of how you would implement each traversal using recursion, then substitute a stack with push on entry and pop on exit for each call.

Which is exactly how it's done at machine level (at least without tail recursion removal).

Thank you for your kind and informative answer!

I just had an exam that asked for pre and post order BST and I couldn't remember which one was which.

Am I destined for ENTERPRISE RUBY?

no. probably doomed for IT aka geek squad. it's obvious from the function name what the order is.

preorder is

int traverse(treeNode *curr) {
    if (curr != NULL) {
        printf("%d", curr->item);
        traverse(curr->left);
        traverse(curr->right);
    }
}

and postorder is moving the curr->item instruction after the recursive calls. simple.

>>2
Of if you want to be an asshole about it, do this without the aid of a stack.

>>5

Let me optimize that for you...


inline int traverse(treeNode *curr) {
    if (curr != NULL) {
        printf("%d", curr->item);
        traverse(curr->left);
        traverse(curr->right);
    }
}

>>7
IHBT

If the tree nodes are doubly-linked, then you don't need a stack.

>>9
need a stack
You do?

(define (traverse f tree)
  (call/ec
   (let walk ((tree tree) (r '()))
     (lambda (k)
       (cond ((null? tree) (k r))
             ((pair? tree)
              ((walk (car tree) r)
               (lambda (v)
                 ((walk (cdr tree) r)
                  (lambda (v2)
                    (k (cons v v2)))))))
             (else (k (f tree))))))))

Amazing, a 5 year old thread is bumped, and it's all but identical to my final programming assignment.

>>10
fuck off, lisper

Bringing /prog/ back to its people
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy