Is there a name and efficient algorithm for this Tree Traversal method?

Question

Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.

I want to traverse this type of tree giving equal opportunity/priority/time(?) for each group with respect to its parent.

For example, if the root have 3 sub-trees (node or leaf), first I want to complete 1 task from the first sub-tree, then complete another task from the second sub-tree, and finally complete a task from the third sub-tree. When all sub-trees processed, the algorithm would start from the beginning this time selecting the second task from the sub-trees. This way, all the sub-trees would have equal processing time in terms of tasks in a given time frame. The same requirement is also present in each sub-trees themselves recursively of course.

This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?

Consider the following tree structure as an example:

So the traversal I am thinking about would be as following for this example.

1. Level 0 has no task, 3 sub-trees, go into first sub-tree to find a task
2. We follow as in depth-first to arrive at task A and select it (complete it)
3. Now the first sub-tree in level 1 has a task completed, while its siblings are at 0, so we select from the second sub-tree
4. Level 1 second sub-tree has only one task, D, so we select it
5. Similarly we go in to the third sub-tree and find the task F and select it
6. Now we return to level 1 and try to find our second task from the first sub-tree
7. IMPORTANT: We have already selected a task from level 1's first sub-tree, so we go into its second sub-tree and select task E
8. Now level 1 first sub-tree has two tasks completed, and the second sub-tree has no other tasks, so we skip it and go into third sub-stree and select G
9. Similary, we loop again and select B from left side, and I from right side (we don't select H because its sibling already selected)
   10. Then we select C from the left side completing this side and K from the right side (J is not selected similarly)
   11. Only the right is left, so we select first H and finally the J, completing our traversal.

Traversal of leaves: (A->D->F)->(E->G)->(B->I)->(C->K)->(H)->(J)

[Adding this clarifying paragraph from the comments:]

Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations.

So my questions are:

1. Is there a name for this kind of tree traversal. If not, what would you call it?

2. How would you approach traversing this tree in an efficient way and what would be the complexity?

Big thanks!

EDIT: Changed "opportunity" to "opportunity/priority/time(?)" in text and removed it from the title.

UPDATE: I have used the final algorithm from Apass.Jack and compared some different trees on it. Calculating the complexity proved difficult, though it definitely looks lower than $O(n\log n)$,.

JS Code can be found as a:

• JS Online Engine: Javascript (Node ES6+) Implementation
• Gist Code: GitHub Gist Source

Here are some execution results for different depths (D) and leaf counts (L):

          D3L10   | D3L1000 | D6L10 | D6L1000
          ===================================
Push      |  35   |   3350  |  50   |  4698 |
Unshift   |  14   |   1150  |  17   |  1549 |
Splice    |  35   |   3350  |  50   |  4698 |
Access    |  35   |   3350  |  50   |  4698 |
Traverse()|  16   |   1351  |  20   |  1808 |
Zip()     |   5   |    151  |   8   |   550 |
          -----------------------------------

NOTE: My question traversed siblings in left to right order but as Apass.Jack has stated below, a randomized recursive round-robin (RRRR) algorithm would indeed be more useful in task-management situation and current algorithm could be modified to do that easily.

Answer 1

If we just mark a leaf as visited in this round instead of removing it so as to allow it to be listed in the next round, we will get an algorithm to traverse tree leaves with repetitions, which is called "recursive round robin scheduler" in the case of binary trees in a paper in Computer Networks in 1999, which I would also call "recursive round robin tree leaf sampling with replacement".

So I would call the output of the algorithm in OP's question "recursive round robin tree leaf sampling without replacement" or "RRR tree leaf traversal" or just "RRR traversal" in short. Indeed, I cannot think of any other algorithm that traverse tree leaves could rightfully claim being both "round robin" at subtrees of the same parent and "recursive".

(If the order in which each subtree of the same parent is selected is randomized instead of always left to right, we will have an algorithm that we may call recursive randomized round robin leaf traversal algorithm, or, an even more lovely abbreviation, RRRR traversal.)

Here is the pseudocode of my recursive algorithm that has the same output as OP's algorithm and its auxiliary zip procedure.

procedure rrrTraversal(rootedTree):
  if rootedTree is just a root without children
    return a list with rootedTree as its only element

  ll := an empty list of lists

  foreach subtree s of rootedTree from left to right:
    ss := rrrTraversal(s)
    push ss to the back of ll

  return zip(ll)

procedure zip(listOflists):
  zipped := an empty list

  while listOflists is not empty:
    foreach list li in listOflists from front to end:
      if li is not empty:
        fi := first item in li
        remove fi from li
        push fi to the back of the zipped
      else:
        remove li from listOflists

  return zipped

OP asks "This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?" The algorithm listed above gives a positive answer to that. It also fully justifies the usage of "recursive" in our description of the algorithm.

This algorithm may be refined by merging a parent with its only child whenever that situation, a parent with only one child, is encountered.

Here is a sample implementation in JavaScript.

The average complexity of the algorithm is probably $O(n\log n)$, because of the similarity of the algorithm to merge sort. However, it is not clear what will be the worst cases and what will be complexity of the worst cases.

It looks like it is nontrivial to find a significant faster algorithm than the recursive algorithm above. In particular, is there a linear algorithm in term of the number of the leaves? That should be a new question, though.

Answer 2

Here is a simple algorithm using a stable priority queue, where elements of equal priority will exit the queue in the order they are inserted into the queue.

1. Let the priority of each node be its level, a.k.a. its depth from the root. Lower level means higher priority.
2. Initialize $Q$ to be a stable priority queue of nodes containing the root.
3. while $Q$ is not empty:
   1. Take a node $q$ from $Q$.
   2. while $q$ is not a leaf:
      1. Add $q$'s next right sibling, if any, to $Q$.
      2. Replace $q$ by its leftmost child.
   3. output $q$.

This traversal goes level by level, outputting the leftmost leaf of each subtree and keeping track of what to do next in each subtree in the stable priority queue. Note that the traversal uses each edge only once.

Here is a sample run of the algorithm.

1
├──2
│  ├──3
│  │  ├──A
│  │  ├──B
│  │  └──6
│  │     └──C
│  └──8
│     └──E
├──D
└──11
   ├──F
   └──13
      ├──14
      │  ├──G
      │  └──H
      ├──17
      │  └──18
      │     ├──I
      │     └──J
      └──K


Queue is not empty: [1]
1 has no more siblings.

Descending to the first child of 1: node 2
Added 2's sibling D to the queue.
The queue is now: [D]

Descending to the first child of 2: node 3
Added 3's sibling 8 to the queue.
The queue is now: [D, 8]

Descending to the first child of 3: node A
Added A's sibling B to the queue.
The queue is now: [D, 8, B]
Output leaf: A


Queue is not empty: [D, 8, B]
Added D's sibling 11 to the queue.
The queue is now: [11, 8, B]
Output leaf: D


Queue is not empty: [11, 8, B]
11 has no more siblings.

Descending to the first child of 11: node F
Added F's sibling 13 to the queue.
The queue is now: [8, 13, B]
Output leaf: F


Queue is not empty: [8, 13, B]
8 has no more siblings.

Descending to the first child of 8: node E
E has no more siblings.
Output leaf: E


Queue is not empty: [13, B]
13 has no more siblings.

Descending to the first child of 13: node 14
Added 14's sibling 17 to the queue.
The queue is now: [B, 17]

Descending to the first child of 14: node G
Added G's sibling H to the queue.
The queue is now: [B, 17, H]
Output leaf: G


Queue is not empty: [B, 17, H]
Added B's sibling 6 to the queue.
The queue is now: [17, 6, H]
Output leaf: B


Queue is not empty: [17, 6, H]
Added 17's sibling K to the queue.
The queue is now: [6, K, H]

Descending to the first child of 17: node 18
18 has no more siblings.

Descending to the first child of 18: node I
Added I's sibling J to the queue.
The queue is now: [6, K, H, J]
Output leaf: I


Queue is not empty: [6, K, H, J]
6 has no more siblings.

Descending to the first child of 6: node C
C has no more siblings.
Output leaf: C


Queue is not empty: [K, H, J]
K has no more siblings.
Output leaf: K


Queue is not empty: [H, J]
H has no more siblings.
Output leaf: H


Queue is not empty: [J]
J has no more siblings.
Output leaf: J

You can play with a JavaScript implementation by Apass.Jack of this algorithm

The only slowdown for this algorithm is the stable priority queue. Using generic stable priority queue will give you $\mathcal{O}(n \log n)$ total runtime, where $n$ is the size of the tree.

However, it is possible to cut the running time down to $\mathcal{O}(n)$. Note that once we take a node with priority $p$ from the top of the queue, we will then possibly add a node with priority $p$, then descend to the child, then possibly add a node with priority $p+1$ and so on. This gives an idea to implement the priority queue as a linked list:

1. Each element of the list is a queue of nodes with the same priority.
2. Top priority is at the head of the list. If we pop last node from the top queue, the head of the list is removed.
3. When we descend to a child, the (candidate) priority is incremented, so we should move through the list, if necessary.
4. When we push new node, we either insert new queue into the list, or push the element to existing one.

Here's the states of such a priority queue from the run above (asterisk means current queue for insertion):

Initial:
└─[1] *

After popping node 1 and descending to node 2:
└─[D] *

After descending to node 3:
├─[D]
└─[8] *

After descending to node A:
├─[D]
├─[8]
└─[B] *

Taking D from the top:
├─[8] *
└─[B]

And pushing 11 before [8] because of greater priority.
├─[11] *
├─[8]
└─[B]

Taking 11 from the top and adding 13, which has the same priority as 8:
├─[8, 13] *
└─[B]

Taking 8 from the top:
├─[13] *
└─[B]

Taking 13 from the top:
└─[B] *

Pushing 17 with the same as B priority:
└─[B, 17] *

Added H to after [B, 17] because we descended:
├─[B, 17]
└─[H] *

Took B from the top:
├─[17] *
└─[H]

Added 6:
├─[17, 6] *
└─[H]

Took 17, added K:
├─[6, K] *
└─[H]

Descended to the child:
├─[6, K]
└─[H] *

Added J to a new queue, because we descended:
├─[6, K]
├─[H]
└─[J] *

Exhausting the rest of the queue:
├─[K] *
├─[H]
└─[J]

├─[H] *
└─[J]

└─[J] *