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 the difference between preorder/postorder in a graph and preorder/postorder in a binary tree. In a binary tree only one preorder and postorder traversal exists, whereas a graph can have many preorder and postorder traversals, since the order in which successors should be expanded is not defined (i.e. there is no concept of left or right child in a general graph). Another difference is 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$
1

Your Answer

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

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