1

Possible Duplicate:
Post order traversal of binary tree without recursion

I was going through the inorder traversal algorithm in a binary tree by Morris. Can someone please suggest whether there is a way to traverse postorder without using recursion and stack?

Community
  • 1
  • 1
Kunal
  • 511
  • 2
  • 6
  • 12
  • There are a couple of answers in [this question](http://stackoverflow.com/questions/1294701/post-order-traversal-of-binary-tree-without-recursion) – Blastfurnace May 21 '12 at 23:55
  • 1
    Does your tree have links from the children to the parent? If so, you can do it with a Visitor. – Blckknght May 21 '12 at 23:57

1 Answers1

2

You can do this with a threaded tree. Here's an outline of the method (taken from here—see slide 31):

  • Postorder: a dummy node created that has root as left descendant.
  • A variable can be used to check type of current action.
  • If action is left traversal and current node has a left descendant, then descendant is traversed. Otherwise action changed to right traversal.
  • If action is right traversal and current node has a left descendant, action changed to left traversal. Otherwise action changed to visiting a node.
  • If action is visiting node: current node is visited, afterwards its postorder successor has to be found.
  • If current node’s parent accessible through a thread (i.e. current node is parent’s left child) then traversal is set to continue with the right descendant of parent.
  • If current node has no right descendant, this is the end of the right-extended chain of nodes.
  • First: the beginning of the chain is reached through the thread of the current node.
  • Second: right references of nodes in the chain is reversed.
  • Finally: chain is scanned backward, each node is visited, then right references are restored to previous settings.

As the above reference goes on to show, it can also be done without threading if you use temporary modifications to the tree structure.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • Is there any more simple way to understand this ? Forgive for my ignorance, but I really wanted to understand it in more simple way. – rgaut Sep 17 '14 at 21:03
  • 1
    @rgaut - I'm not sure that there's a simpler path to understanding this. Postorder traversal without a stack (or recursion, which is an implicit stack) just involves a lot of careful bookkeeping. It might be easier to understand using a simple but non-trivial example together with some diagrams of what's happening at each step of the algorithm. – Ted Hopp Sep 18 '14 at 02:46