title: Understanding Wikipedia code for a generic depth-first tree search?
body: <p>I was brushing up on different tree traversal methods and ended up reading the following Wikipedia <a href="http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_traversal" rel="nofollow">article</a>. As expected, there are three methods of depth first traversal for a binary tree:  </p>
  
  <ol>
  <li>Preorder traversal  </li>
  <li>Postorder traversal  </li>
  <li>Inorder traversal  </li>
  </ol>
  
  <p>The article then goes on to deal with depth first traversal of an arbitrary (generic) tree. I have pasted it here for convenience:  </p>
  
  <pre><code>// To traverse a non-empty tree in depth-first order,
  // perform the following operations recursively at each node:
  Perform pre-order operation
  for i=1 to n-1 do
      Visit child[i], if present
      Perform in-order operation
  
  Visit child[n], if present
  Perform post-order operation
  </code></pre>
  
  <p>Here is all the explanation that Wikipedia provides:  </p>
  
  <blockquote>
    <p>where n is the number of child nodes. Depending on the problem at
    hand, the pre-order, in-order or post-order operations may be void, or
    you may only want to visit a specific child node, so these operations
    should be considered optional. Also, in practice more than one of
    pre-order, in-order and post-order operations may be required. For
    example, when inserting into a ternary tree, a pre-order operation is
    performed by comparing items. A post-order operation may be needed
    afterwards to rebalance the tree.</p>
  </blockquote>
  
  <p>The algorithm specified makes no sense to me since it is specified in terms of undefined operations:  </p>
  
  <ol>
  <li>A preorder operation.  </li>
  <li>A postorder operation.  </li>
  <li>An inorder operation.  </li>
  </ol>
  
  <p>To add to the confusion, I can't come up with a definition for the said operations based on what I know and what is present in the Wikipedia article. I have been puzzling over this for a while with no real breakthroughs. I have the following questions:  </p>
  
  <ol>
  <li>Is the algorithm specified in the Wikipedia article wrong? I suspect it is, but can't say anything for certain beyond the fact that it is ill-specified.  </li>
  <li>Are a postorder, preorder, inorder depth first traversal even defined for a generic tree? Are these practically used? Does it relate to the definition of the three operations? If so, how?  </li>
  <li>If the algorithm is indeed correct, can someone define the above operations for me and explain how it works?   </li>
  </ol>