Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.
share|improve this question
1  
If you want a specific proof, you should describe the algorithms exactly (or give reference to exact descriptions)... –  tomasz Aug 12 '12 at 21:09
    
oops my apologies, I thought it was a very general algorithm. I'll add it now –  sandman001 Aug 12 '12 at 21:15

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.