I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition.
I'm not quite sure where to start..
Any help would be much appreciated :)
Preorder(T) algorithm
- Print the root $r$.
- If $r$ has children then let $x_0,\dots,x_n$ be all the children of $r$, in left-to-right order.
- Set $T_i$ to be the subtree whose root is $x_i$ for $i = 0,\dots,n$.
- While $i\le n$ do $\text{preorder}(T_i)$.
Postorder(T) algorithm
- Set $c = r$.
- If $c$ has children then let $x_0,\dots,x_n$ be all the children of $c$ in the left-to-right order.
- Set $T_i$ to be the subtree whose root is $x_i$ for $i = 0,\dots,n$.
- While $i\le n$ do $\text{postorder}(T_i)$.
- Print $c$.