3
$\begingroup$

I'm somewhat confused about the Wikipedia terms about the meaning of 'reversed' in the context of tree & graph treversals

Suppose I have a tree:

         1
        / \
       /   \
      /     \
     /       \
    2         3
   / \       /
  4   5     6
 / \       / \
7   8     9  10

Tree traversal article describes reversed traversal as going right-to-left as opposed to left-to-right;

so according to it the tree has preorder traversal

1 2 4 7 8 5 3 6 9 10

and reverse preorder traversal

1 3 6 10 9 2 5 4 8 7

However, the DFS article describes reverse orderings as just the reversed version of a usual one (while left-to-right vs. right to-left is AFAIU left undefined);

so according to this article both of the above are preorderings, while

10 9 6 3 5 8 7 4 2 1 is the reverse preordering for the 1st one, and

7 8 4 5 2 9 10 6 3 1 is the reverse preordering for the 2nd one.

(I realize the last two are the two post-order traversals in the first article's sense.)

So, are there two different terminologies in contexts of trees and general graphs respectively? Isn't there a mistake in some of these articles?

If there's no mistake, then, if asked to find a reverse preorder of a given graph (tree), I guess I should clarify which meaning of 'reverse' a person implies, right?

$\endgroup$

1 Answer 1

3
$\begingroup$

You are right. "Reverse" in the context of binary trees does not mean the same as "reverse" in the context of general graphs. In general graphs, "reverse" preorder/postorder simply means putting the nodes in the opposite order as they appear in the normal preorder/postorder trace. For example, if the preorder trace is A, B, C, D, the reverse preorder trace will be D, C, B, A. The same goes for postorder. However, in binary trees, it means a different thing; swapping left and right child nodes in the recurrence relations (or going right-to-left instead of left-to-right):

Preorder:          root, (left), (right)
Reverse preorder:  root, (right), (left)

Postorder:         (left), (right), root
Reverse postorder: (right), (left), root

# this ordering only exists in binary trees
Inorder:           (left), root, (right)
Reverse inorder:   (right), root, (left)

Notice that (node) means to recursively apply the ordering to the specified node.

Also, bear in mind that with general graphs, one has to take care of preventing cycles and handling disconnected components, which by definition, do not occur in a tree:

A tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

$\endgroup$
2
  • 1
    $\begingroup$ To further confusion, for binary trees: reverse preorder is postorder in reverse. As is witnessed by your recursive definitions. $\endgroup$ Commented Jul 10, 2022 at 11:48
  • $\begingroup$ And similarly, for binary trees: reverse postorder is preorder in reverse, as witnessed by the recursive definitions. Thanks for the link @HendrikJan! I hadn't thought about it. $\endgroup$
    – mateleco
    Commented Jun 8 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.