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$.
  • 0
    oops my apologies, I thought it was a very general algorithm. I'll add it now2012-08-12

1 Answers 1

1

I would do it by strong induction on the height of the tree. A tree of zero height has one node-you should be able to show that it prints that node and stops. Then assume all trees of height $\le n$ are printed correctly. Given a tree of height $n+1$, when you call the other preorders they do not include the root, so it will not be repeated, and they will be printed correctly.