Suppose we have a (binary)tree $T$. The postorder traversal of a tree is described here, let's call it $LRR$ (Left, Right, Root) traversal.
Now suppose we keep the visted nodes in a $LRR$ traversal in a vector $v$. It seems that the vector $v$ can be obtain by using a $RRL$ (Root, Right, Left) traversal of the same binary tree, which gives us, let's say the vector $p$ of visited nodes in such a traversal. Then the vector $v$ is the reversed vector $p$.
Is this true? Is it also true for any tree, not necessarily a binary one ?
I think it is true in the case of Binary trees. We will prove this by induction on the height of the tree. Clearly this is true when the height is just $1$. Now suppose it is true upto height $n$ and we want to prove it for height $n+1$.
Let $T_{n+1}$ denote the tree. Let the root be $r_{n+1}$ and left branch be $L_{n+1}$ and right branch be $R_{n+1}$. Now the traversal gives the vector $r_{n+1}v(R_{n+1})v(L_{n+1})$. But in the postorder traversal we get $w(L_{n+1})w(R_{n+1})r_{n+1}$ and we know that $w(L_{n+1})$ is reverse of $v(L_{n+1})$.