0
$\begingroup$

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

  1. Print the root $r$.
  2. If $r$ has children then let $x_0,\dots,x_n$ be all the children of $r$, in left-to-right order.
  3. Set $T_i$ to be the subtree whose root is $x_i$ for $i = 0,\dots,n$.
  4. While $i\le n$ do $\text{preorder}(T_i)$.

Postorder(T) algorithm

  1. Set $c = r$.
  2. If $c$ has children then let $x_0,\dots,x_n$ be all the children of $c$ in the left-to-right order.
  3. Set $T_i$ to be the subtree whose root is $x_i$ for $i = 0,\dots,n$.
  4. While $i\le n$ do $\text{postorder}(T_i)$.
  5. Print $c$.
  • 1
    If you want a specific proof, you should describe the algorithms exactly (or give reference to exact descriptions)...2012-08-12
  • 0
    oops my apologies, I thought it was a very general algorithm. I'll add it now2012-08-12

1 Answers 1