1
$\begingroup$

I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name.

The requirements of the algorithm are:

  1. it visits the parent before the children.
  2. it visits all the children in one group.
  3. it is otherwise depth-first.

I basically modified a pre-order to visit the siblings all together, before going down to the child of the first sibling. Note that this is not breadth-first.

Here is an example of the traversal order:

enter image description here

As you can see, in this tree, the traversal would be H, D, L, B, F, A, C, E, G, J, N, I, K, M, O, and grouping for siblings: (H), (D, L), (B, F), (A, C), (E, G), (J, N), (I, K), (M, O).

Some things to ponder:

  • I think one can also view this as a pre-order traversal of the "dual" of this tree, where the dual nodes are representative of each group of siblings.
  • Notice the z-shapes. It is like a "z-order-traversal", an analog to a z-order-curve, but for tree traversal. It has the similar property of traversing children together, just like a z-order curve will visit the siblings of the finest level of a full quadtree.

So, what is the name of this traversal order?

$\endgroup$
  • $\begingroup$ Yes, I would just call this pre-order, for the reason you state. Except that when a node is "visited" we actually look at its two children instead. $\endgroup$ – Hendrik Jan Nov 10 '15 at 17:44
  • $\begingroup$ @HendrikJan well it is a type of pre-order, I was hoping for a more specific name, given its additional properties? $\endgroup$ – Realz Slaw Nov 10 '15 at 19:36
  • 1
    $\begingroup$ Well my view is that it is pre-order (with a twist). In pre-order each node is visited and some task is performed. Here the task is looking at the two children. I know, that is not competely fair, but too close to pre-order to look for another name. (But I like the intuitive Z-order you suggest too) $\endgroup$ – Hendrik Jan Nov 11 '15 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.