Understanding Wikipedia code for a general tree depth search?

Question

I combed on different tree traversal methods and ended up reading the next Wikipedia article . As expected, there are three methods for first traversing depth for a binary tree:

• Bypass order
• Post processing
• Bypass on the way

Further in the article, an attempt is made to deal with the depth of the first traversal of an arbitrary (common) tree. I inserted it here for convenience:

// 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 

Here is the whole explanation Wikipedia offers:

where n is the number of child nodes. Depending on the problem, the pre-order, order or post-order operations may be invalid or you may only need to visit a specific child of the node, so these operations should be considered optional. In addition, in practice, more than one of them may require preliminary, operational and post-warrant operations. For example, when pasted into a triple tree, a pre-order operation is performed by comparing the elements. Post-order operation may then be required to rebalance the tree.

The specified algorithm does not make any sense to me, since it is indicated in terms of undefined operations:

• Pre-order operation.
• Operation after order.
• Operation inorder.

To add to the confusion, I cannot find a definition for these operations based on what I know and what is present in the Wikipedia article. I have been puzzled by this for some time without real breakthroughs. I have the following questions:

• Is the algorithm specified in the Wikipedia article incorrect? I suspect this is so, but cannot say anything definite except that it is poorly specified.
• Are post-processing, pre-ordering, first-order depths, even specific to a common tree? Are they used in practice? Is this related to the definition of three operations? If so, how?
• If the algorithm is really correct, can someone define the above operations for me and explain how it works?

Answer 1

The specified algorithm is really correct. What happens in this case is that the Wikipedia article contains one piece of code that handles the general case, which handles pre-order, order and post-processing in one.

You may think that preorder, inorder and postorder bypass everything as special cases of a more general algorithm. In particular, suppose you want to traverse a tree and perform some operation at a specific time during a search (for both preliminary and order). One way to think about this is that you perform some preliminary operation before visiting the current node, some inorder between visiting the child of the node and the node itself and some post-operation after visiting the node. Any of these operations may be “do nothing”. For example, a simple pre-order bypass will be listed as

• Pre-order step: complete the operation that you want to perform pre-order.
• Order Pitch: No-op
• Post-Step Step: No-op

Similarly, post-order workaround will be

• Pre-order Step: No-op
• Order Pitch: No-op
• Step in order: perform the operation you want to perform after <

The advantage of Wikipedia code is that it allows you to perform operations that require both a preliminary and a post-order step. For example, suppose you want to perform a tree search, but at each point in time you are tracking which nodes have been visited but not yet completed. You can do it as follows:

• Pre-order step: add the current node to the "active" list.
• Order Pitch: No-op
• Post-installation step: remove the current node from the "active" list.

Some algorithms, such as the Tarjan SCC algorithm , actually do such things (although, admittedly, the graph algorithm and the question relate to trees). Thus, the Wikipedia code provides a general case where more common cases, as well as this more complex case, are special cases.

Hope this helps!