Are reversed reverse preorder traversals equivalent to a postorder traversal?

Question

I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse preorder traversal (because it is considerably easier to implement iteratively), and then reversing the output. To my further surprise, I could not find a single counterexample to these conjectures, which I will state clearly:

• Conjecture 1: The post-order traversal of a tree $T$ is equivalent to the reversed reverse pre-order traversal of $T$.

• Conjecture 2: The reverse post-order traversal of a tree $T$ is equivalent to the reversed pre-order traversal of $T$.

I thought about this plenty, and came up with an extremely informal justification for this: LRN = reverse(NRL) and RLN = reverse(NLR). Not sure if this is purely coincidental or not. Can anybody either provide a proof of either conjecture? Furthermore, if true, do these conjectures extend to any arbitrary graph/digraph?

Answer 1

This can be proven by induction on trees. I give details on the conjecture 1 here.

• It is clearly true for the empty tree and for leaves;
• Suppose it is true for trees $l$ and $r$. Consider $t$ a node with $l$ and $r$ as left and right children, and $x$ as root. Then, if we denote $Rpre(t)$ the reverse pre-order of $t$, $post(t)$ the post-order of $t$, and $\overline{seq}$ the reversed sequence of $seq$, we get:

$$Rpre(t) = x\cdot Rpre(r)\cdot Rpre(l) = x\cdot \overline{post(r)}\cdot \overline{post(l)} = \overline{post(l)\cdot post(r)\cdot x} = \overline{post(t)}$$

The conjecture 2 is proven in the same way.

I doubt there is an equivalent property for graphs because children are unordered in graphs (but I may be wrong…)

Answer 2

Nathaniels simple and elegant proof is the best way to formally convince yourself your conjectures are true. I want to add a more informal and visual explanation.

The postorder traversal of a binary tree can be found following an Euler traversal of the tree. That is, we follow the path along the tree starting at the root, counterclockwise, noting the vertex at its last visit (postorder) which is represented by the green dot below.

If we look at the reverse pre-order, we follow the same Euler tour, but clockwise (as we visit the right subtree before the left one) and we note each vertex at its first visit: which is now also the green dot.

Hence the reverse pre-order is the post-order in reverse.